Search

We show abstract versions for Banach couples of several limiting compact interpolation theorems established by Edmunds and Opic for couples of Lp spaces.

Let c e IN. For d e ℤ with gcd (d, c) = 1 let δ(d, c) be defined by d · δ(d, c) 1 mod c, 1 ⩽ δ(d, c) ⩽ c. Let s, t e IN with 1 ⩽ s ⩽ c, 1 ⩽ t ⩽ c. The main result is that for arbitrary fixed e > 0, but uniformly over c, s and t Equivalently, the points (d, δ(c,d)) are approximately uniformly distributed in [0, c] × [0, c]: The two-dimensional discrepancy of {(d,δ (c, d)): 1 ⩽ d ⩽ c and (c, d)= 1} in [0,c] × [0,c] is Oe(ce-1/2).

n/a

This paper studies the virtual $\chi_{-y}$-genera of Grothendieck's Quot schemes on surfaces, thus refining the calculations of the virtual Euler characteristics by Oprea-Pandharipande. We first prove a structural result expressing the equivariant virtual $\chi_{-y}$-genera of Quot schemes universally in terms of the Seiberg-Witten invariants. The formula is simpler for curve classes of Seiberg-Witten length $N$, which are defined in the paper. By way of application, we give complete answers in the following cases: (i) arbitrary surfaces for the zero curve class, (ii) relatively minimal elliptic surfaces for rational multiples of the fiber class, (iii) minimal surfaces of general type with $p_g>0$ for any curve classes. Furthermore, a blow up formula is obtained for curve classes of Seiberg-Witten length $N$. As a result of these calculations, we prove that the generating series of the virtual $\chi_{-y}$-genera are given by rational functions for all surfaces with $p_g>0$, addressing a conjecture of Oprea-Pandharipande. In addition, we study the reduced $\chi_{-y}$-genera for $K3$ surfaces and primitive curve classes with connections to the Kawai-Yoshioka formula., Comment: 48 pages. Reformulation of Theorem 1 for readability. Extra explanation for the mixed terms in section 2.2.3. Reference updates

We survey results about Haar null subsets of (not necessarily locally compact) Polish groups. The aim of this paper is to collect the fundamental properties of the various possible definitions of Haar null sets, and also to review the techniques that may enable the reader to prove results in this area. We also present several recently introduced ideas, including the notion of Haar meager sets, which are closely analogous to Haar null sets. We prove some results in a more general setting than that of the papers where they were originally proved and prove some results for Haar meager sets which were already known for Haar null sets.

In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborova, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten-Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulie, Mossel et al., and Bordenave, Lelarge, and Massoulie proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi-linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message-passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information-computation gaps. © 2017 Wiley Periodicals, Inc.

Shannon and Zipf-Mandelbrot entropies have many applications in many applied sciences, for example, in information theory, biology and economics, etc. In this paper, we consider two refinements of the well-know Jensen inequality and obtain different bounds for Shannon and Zipf-Mandelbrot entropies. First of all, we use some convex functions and manipulate the weights and domain of the functions and deduce results for Shannon entropy. We also discuss their particular cases. By using Zipf-Mandelbrot laws for different parameters in Shannon entropies results, we obtain bounds for Zipf-Mandelbrot entropy. The idea used in this paper for obtaining the results may stimulate further research in this area, particularly for Zipf-Mandelbrot entropy.

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

This paper addresses the sharpness of a weighted $L^{2}$-estimate for the Fourier extension operator associated to the circle, obtained by J. Bennett, A. Carbery, F. Soria and A. Vargas in 2006. A point left open in their paper was the necessity of a certain $\log R$-factor in the bound. Here, I show that the factor is necessary for all $1/2$-Ahlfors-David regular weights on the circle, but it can be removed for $s$-Ahlfors-David regular weights with $s \neq 1/2$., 12 pages

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016

In this paper we deal with the hyponormality of Toeplitz operators with matrix-valued symbols. The aim of this paper is to provide a tractable criterion for the hyponormality of bounded-type Toeplitz operators (i.e., the symbol is a matrix-valued function such that Φ and are of bounded type). In particular, we get a much simpler criterion for the hyponormality of when the co-analytic part of the symbol Φ is a left divisor of the analytic part.

We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014

In this paper, we discuss hybrid point sets built from two of the most prominent classes of sequences used in quasi-Monte Carlo methods. We derive an existence result on point sets with low diaphony, where the components of the points involved stem from a digital (t, s)-sequence on the one hand, and from a lattice point set on the other. Moreover, we outline how the hybrid diaphony of the point sets considered in this paper relates to the worst-case integration error in suitable function spaces.

The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n] = {1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.

In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + mp ≤ D(Gn) ≤ n + mp + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and mp depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(Gn) = n + mp (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m - n ≫ n2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters m and n among all such digraphs with positive in/out-degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

Starting with a paper of Jacobson from the 1960s, many authors became interested in characterizing all algebraic number fields in which each integer is the sum of pairwise distinct units. Although there exist many partial results for number fields of low degree, a full characterization of these number fields is still not available. Narkiewicz and Jarden posed an analogous question for sums of units that are not necessarily distinct. In this paper we propose a generalization of these problems. In particular, for a given rational integer n we consider the following problem. Characterize all number fields for which every integer is a linear combination of finitely many units e i in a way that the coefficients a i ∈ℕ are bounded by n . The paper gives several partial results on this problem. In our proofs we exploit the fact that these representations are related to symmetric beta expansions with respect to Pisot bases.

In this paper we study a class of elliptic second-order differential operators on finite dimensional convex compact sets whose principal part degenerates on a subset of the boundary of the domain. We show that the closures of these operators generate Feller semigroups. Moreover, we approximate these semigroups by iterates of suitable positive linear operators which we also introduce and study in this paper for the first time, and which we refer to as modified Bernstein-Schnabl operators. As a consequence of this approximation we investigate some regularity properties preserved by the semigroup. Finally, we consider the special case of the finite dimensional simplex and the well-known Wright-Fisher diffusion model of gene frequency used in population genetics. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

For a flnite group G let i(G) denote the graph deflned on the non- identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. In this paper it is shown that the graph i(G) contains a Hamiltonian cycle for many flnite groups G. In the literature many deep results about flnite simple groups G can equivalently be stated as theorems about i(G). Three examples are given. Guralnick and Shalev (10) showed that for su-ciently large G the graph i(G) has diameter at most 2. Guralnick and Kantor (9) showed that there is no isolated vertex in i(G). Finally, Breuer, Guralnick, Kantor (4) showed that the diameter of i(G) is at most 2 for all G. In this paper those flnite groups G are considered for which i(G) contains a Hamiltonian cycle. The following proposition reduces the investigations to those non-solvable groups G for which G=N is cyclic for any non-trivial normal subgroup N of G. Proposition 1.1. Let G be a flnite solvable group that has at least 4 elements. Then the graph i(G) contains a Hamiltonian cycle if and only if G=N is cyclic for all non-trivial normal subgroups N of G. The three main results of this paper are Theorems 1.2, 1.3, and 1.4.

Two fundamental questions in the theory of Groebner bases are decision ("Is a basis G of a polynomial ideal a Groebner basis?") and transformation ("If it is not, how do we transform it into a Groebner basis?") This paper considers the first question. It is well-known that G is a Groebner basis if and only if a certain set of polynomials (the S-polynomials) satisfy a certain property. In general there are m(m-1)/2 of these, where m is the number of polynomials in G, but criteria due to Buchberger and others often allow one to consider a smaller number. This paper presents two original results. The first is a new characterization theorem for Groebner bases that makes use of a new criterion that extends Buchberger's Criteria. The second is the identification of a class of polynomial systems G for which the new criterion has dramatic impact, reducing the worst-case scenario from m(m-1)/2 S-polynomials to m-1., 20 pages, 2 figures

Since the development of the calculus of variations there has been interest in finding critical points of functionals. This was intensified by the fact that for many equations arising in practice, the solutions are critical points. In searching for such points, there is a distinct advantage if the functional G is semibounded. In this case one can find a Palais-Smale (PS) sequence G (uk) c, G ′(uk) 0 or even a Cerami sequence G (uk) c, (1 + ‖uk ‖)G ′(uk) 0. These sequences produce critical points if they have convergent subsequences. However, there is no clear method of finding critical points of functionals which are not semibounded. Linking subsets do provide such a method. They can produce a PS sequence provided they separate the functional. In previous papers we have shown that there are pairs of subsets that can produce Cerami-like sequences even though they do not separate the functional. We call such sets sandwich pairs. All that is required is that the functional be bounded from above on one ofthe sets and bounded from below on the other, with no relationship needed between the bounds. This provides a distinct advantage in applications. The present paper discusses the situation in which one cannot find linking subsets which separate the functional or sandwich pairs for which the functional is bounded below on one set and bounded above on the other. We develop a method which can deal with such situations. We apply the method to problems in partial differential equations (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

This paper continues the work started in [E. Kissin, V. S. Shulman and Yu. V. Turovskii, �Banach Lie algebras with Lie subalgebras of finite codimension: their invariant subspaces and Lie ideals�, J. Funct. Anal. 256 (2009) 323�351.] and is devoted to the study of reducibility of an infinite-dimensional Lie algebra of operators on a Banach space when its Lie subalgebra of finite codimension has an invariant subspace of finite codimension. In addition to the tools developed in the above paper; filtrations of Banach spaces with respect to Lie algebras of operators and related systems of operators on graded Banach spaces, the present paper introduces and studies some new concepts and techniques: the theory of Lie quasi-ideals and properties of Lie nilpotent finite-dimensional subspaces of Banach associative algebras. The application of these techniques to an operator Lie algebra L shows that, under some mild additional assumptions, L is reducible if its Lie subalgebra of finite codimension has an invariant subspace of finite codimension. This, in turn, leads to the main result of the paper: if a Banach Lie algebra L has a closed Lie subalgebra of finite codimension, then it has a proper closed Lie ideal of finite codimension. Moreover, if L is non-commutative, then it has a characteristic Lie ideal of finite codimension, that is, a proper closed Lie ideal of L invariant for all bounded derivations of L.

This thesis consists of three papers, all of them on the topic of function spaces on fractals.The papers summarised in this thesis are:Paper I Mats Bodin, Wavelets and function spaces on Mauldin-Williams fractals, Research Report in Mathematics No. 7, Umea University, 2005.Paper II Mats Bodin, Harmonic functions and Lipschitz spaces on the Sierpinski gasket, Research Report in Mathematics No. 8, Umea University, 2005.Paper III Mats Bodin, A discrete characterisation of Lipschitz spaces on fractals, Manuscript.The first paper deals with piecewise continuous wavelets of higher order in Besov spaces defined on fractals. A. Jonsson has constructed wavelets of higher order on fractals, and characterises Besov spaces on totally disconnected self-similar sets, by means of the magnitude of the coefficients in the wavelet expansion of the function. For a class of fractals, W. Jin shows that such wavelets can be constructed by recursively calculating moments. We extend their results to a class of graph directed self-similar fractals, introduced by R. D. Mauldin and S. C. Williams.In the second paper we compare differently defined function spaces on the Sierpinski gasket. R. S. Strichartz proposes a discrete definition of Besov spaces of continuous functions on self-similar fractals having a regular harmonic structure. We identify some of them with Lipschitz spaces introduced by A. Jonsson, when the underlying domain is the Sierpinski gasket. We also characterise some of these spaces by means of the magnitude of the coefficients of the expansion of a function in a continuous piecewise harmonic base.The last paper gives a discrete characterisation of certain Lipschitz spaces on a class of fractal sets. A. Kamont has discretely characterised Besov spaces on intervals. We give a discrete characterisation of Lipschitz spaces on fractals admitting a type of regular sequence of triangulations, and for a class of post critically finite self-similar sets. This shows that, on some fractals, certain discretely defined Besov spaces, introduced by R. Strichartz, coincide with Lipschitz spaces introduced by A. Jonsson and H. Wallin for low order of smoothness.

In this paper we work in separated locally convex spaces where we give equivalent statements for the formulae of the conjugate function of the sum of a convex lower-semicontinuous function and the precomposition of another convex lower-semicontinuous function which is also K -increasing with a K -convex K -epi-closed function, where K is a nonempty closed convex cone. These statements prove to be the weakest constraint qualifications given so far under which the formulae for the subdifferential of the mentioned sum of functions are valid. Then we deliver constraint qualifications inspired from them that guarantee some conjugate duality assertions. Two interesting special cases taken from the literature conclude the paper. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

This paper gives a complete characterization of those sequences of subword complexity (k −1)n+1 which are natural codings of orbits of k-interval exchange transfor- mations, thereby answering an old question of Rauzy. Interval exchange transformations were originally introduced by Oseledec (17), following an idea of Arnold (1), see also (9); an exchange of k intervals, denoted throughout this paper by I, is given by a probability vector of k lengths (�1,...,�k) together with two permutations (�0,�1) on k letters. The unit interval is partitioned into k subintervals of lengths �1,...,�k which are ordered according to � −1 0 and then rearranged by I according to � −1

Let G be a connected reductive algebraic group with a Frobenius morphism F: G → G defined over a finite field □ pr . The main result of the paper is to prove that any rational G-module M which is projective when restricted to the Frobenius kernel G r = Ker(F) is also projective over the split and twisted finite Chevalley groups. In 1987, Parshall conjectured this statement for r = 1 in the split case. The authors verified this in 1999 with the possible exclusion of primes 2 and 3 in non-simply laced cases. The converse of the main result is also discussed for split groups in this paper.

This article presents a semigroup approach for the mathematical analysis of the inverse coefficient problems of identifying the unknown coefficient k(u(x, t)) in the quasi-linear parabolic equation u t (x, t) = (k(u(x, t))u x (x, t)) x , with Dirichlet boundary conditions u(0, t) = ψ 0 , u(1,t) = ψ 1 . The main purpose of this paper is to investigate the distinguishability of the input-output mappings Φ[·]: K →C 1 [0, T], Ψ[·]: Κ → C 1 [0, T] via semigroup theory. In this paper, it is shown that if the null space of the semigroup T(t) consists of only zero function, then the input-output mappings Φ[·] and Ψ[·] have the distinguishability property. It is also shown that the types of the boundary conditions and the region on which the problem is defined play an important role in the distinguishability property of these mappings. Moreover, under the light of measured output data (boundary observations) f(t):=k(u(0, t))u x (0, t) or/and h(t):=k (u(1,t))u x (1, t), the values k(ψ 0 ) and k(ψ 1 ) of the unknown diffusion coefficient k(u(x,t)) at (x, t) = (0,0) and (x,t) = (1,0), respectively, can be determined explicitly. In addition to these, the values k u (ψ 0 ) and k u (ψ 1 ) of the unknown coefficient k(u(x, t)) at (x,t)=(0,0) and (x, t) = (1, 0), respectively, are also determined via the input data. Furthermore, it is shown that measured output data f(t) and h(t) can be determined analytically by an integral representation. Hence the input-output mappings Φ[·]:Κ→ C 1 [0, T], Ψ[·]:K→ C 1 [0, T] are given explicitly in terms of the semigroup.

We prove, correct and extend several results of an earlier paper of ours (using and recalling several of our later papers) about the derived functors of projective limit in abelian categories. In particular we prove that if C is an abelian category satisfying the Grothendieck axioms AB3 and AB4* and having a set of generators then the first derived functor of projective limit vanishes on so-called Mittag-Leffler sequences in C. The recent examples given by Deligne and Neeman show that the condition that the category has a set of generators is necessary. The condition AB4* is also necessary, and indeed we give for each integer $m \geq 1$ an example of a Grothendieck category Cm and a Mittag-Leffler sequence in Cm for which the derived functors of its projective limit vanish in all positive degrees except m. This leads to a systematic study of derived functors of infinite products in Grothendieck categories. Several explicit examples of the applications of these functors are also studied.

The paper defines a new type of product of association schemes (and of the related objects, permutation groups and orthogonal block structures), which generalizes the direct and wreath products (which are referred to as 'crossing' and 'nesting' in the statistical literature). Given two association schemes for , each having an inherent partition (that is, a partition whose equivalence relation is a union of adjacency relations in the association scheme), a product of the two schemes is defined, which reduces to the direct product if or , and to the wreath product if and , where and are the relation of equality and the universal relation on . The character table of the crested product is calculated, and it is shown that, if the two schemes and have formal duals, then so does their crested product (and a simple description of this dual is given). An analogous definition for permutation groups with intransitive normal subgroups is created, and it is shown that the constructions for association schemes and permutation groups are related in a natural way. The definition can be generalized to association schemes with families of inherent partitions, or permutation groups with families of intransitive normal subgroups. This time the correspondence is not so straightforward, and it works as expected only if the inherent partitions (or orbit partitions) form a distributive lattice. The paper concludes with some open problems.

In this paper, the theory of e-constants associated to tame finite group actions on arithmetic surfaces is used to define a Brauer group invariant µ(X ,G , V) associated to certain symplectic motives of weight one. The relationship between this invariant and w2(π) (the Galois-theoretic invariant associated to tame covers of surfaces defined by Cassou-Nogues, Erez and Taylor) is also discussed. In his paper (4), Deligne used elements in the Brauer group of Q and their relation- ship with certain e-constants to give a proof of the Frohlich-Queyrut theorem. In particular, he showed that certain global orthogonal root numbers are equal to one, by interpreting the associated local orthogonal root numbers as Stiefel-Whitney classes and then using the local root numbers to define an element of order two in the Brauer group of Q. This idea was furthered by Saito (in (13), for example) and others who defined Brauer group invariants associated to situations which can be interpreted as motives that are orthogonal and of even weight. In this paper, we define a Brauer group invariant associated to certain motives that are symplectic and have weight one. In order to construct the relevant motives, we first define X to be an arithmetic surface of dimension two which is flat, regular, and projective over Z. Throughout this paper, we assume that f : X− →Spec(Z) is the structure morphism. Let G be a finite group that acts tamely on X. In other words, for each closed point x ∈ X, the order of the inertia group of x is relatively prime to the residue characteristic of x .L etY be the quotient scheme X /G, which we assume is regular, and assume that for all finite places v, the fiber Yv =( Xv)/G = Y⊗ Z (Z/p(v)) has normal crossings and smooth irreducible components with multiplicities relatively prime to the residue characteristic of v. Finally, let V be a virtual representation of G over

In this paper we construct a representation of the blob algebra [22] over a ring allowing base change to every interesting (i.e. non–semisimple) specialisation which, in quasihereditary specialisations, passes to a full tilting module. The Temperley–Lieb algebras are a tower T0(q) ⊂ T1(q) ⊂ .. of one–parameter finite dimensional algebras [28], each with a basis independent of q. These algebras are quasihereditary [3, 8] except in case q+q = 0. Accordingly one may in principle construct tilting modules, full tilting modules, and corresponding Ringel duals. In fact, if V is a free module of rank 2 over the ground ring then Tn(q) has an action on V , and it is straightforward to show (see later) that V ⊗n is a full tilting module in the quasihereditary cases. Since V ⊗n exists over the ground ring, the Ringel dual can be constructed without having to pick a specialisation. The cases of n finite of this dual are a nested sequence of quotients of the quantum group Uqsl2 [17, 11]. This q–deformable duality and glorious limit structure [16] (more usually observed with Uqsl2 as the starting point) provides the mechanism for massive exchange of representation theoretic information between the two sides [26, 10, 13, 4, 18]. In particular the weight theory of Uqsl2 controls the representation theory of Tn(q) for all n simultaneously (as localisations of a global limit). The blob algebras are a tower b0 ⊂ b1 ⊂ .. of two–parameter finite dimensional algebras (and bn ⊃ Tn(q)). They are quasihereditary except at a finite set of parameter values. Accordingly one may in principle construct tilting modules and so on. Ab initio one would have to expect such a construction to depend on the specialisation, as indecomposable tilting modules do [24]. On the other hand, it turns out [23] that bn has an action on V , and in this paper we show that V ⊗2n is a full tilting module in the quasihereditary cases. Historically, Tn(q) and Uqsl2 were studied extensively separately, before the full tilting module/Ringel duality connection was known, but if one side, and the appropriate full tilting module, had been discovered first, the passage to the Ringel dual would rightly have been regarded as quite a significant spin–off! The bn tilting property of V ⊗2n is a striking result, in as much as it places us in a position analogous to this (as it were, before the discovery of quantum groups).

The isomorphism problem for circulant graphs (Cayley graphs over the cyclic group) which has been open since 1967 is completely solved in this paper. The main result of the paper gives an efficient isomorphism criterion for circulant graphs of arbitrary order. This result also solves an isomorphism problem for colored circulant graphs and some classes of cyclic codes.

In this paper, the components in the stable model of X0(125) over C5 are determined by constructing (in the language of R. Coleman's ‘Stable maps of curves’, to appear in the Kato Volume of Doc. Math.) an explicit semi-stable covering. Empirical data is then offered regarding the placement of certain CM j-invariants in the supersingular disk of X(1) over C5, which suggests a moduli-theoretic interpretation for the components of the stable model. The paper then concludes with a conjecture regarding the stable model of X0(p3) for p > 3, which is as yet unknown.

This paper provides first tools for generalizing the theory of orthogonal rational functions on the unit circle created by Bultheel, Gonzalez-Vera, Hendriksen and Njastad to the matrix case. A crucial part in this generalization is the definition of the spaces of matrix-valued rational functions for which an orthogonal basis is to be constructed. An important feature of the matrix case is that these spaces will be considered simultaneously as left and right modules over the algebra ℂq×q. In this modules we will define simultaneously left and right matrix-valued inner products with the aid of a nonnegative Hermitian-valued q × q Borel measure on the unit circle. Given a sequence (αj)j∈ℕ of complex numbers located in ℂ\ (especially in “good position” with respect to the unit circle) we will introduce a concept of rank for nonnegative Hermitian-valued q × q Borel measures on the unit circle which is based on the Gramian matrix of particular rational matrix-valued functions with prescribed pole structure. A main result of this paper is that this concept of rank is universal. More precisely, it turns out that the rank of a matrix measure does not depend on the given sequence (αj)j∈ℕ. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

Inspired by the work of Bloch and Kato in [ 2 ], David Burns constructed several ‘equivariant Tamagawa invariants’ associated to motives of number fields. These invariants lie in relative $K$ -groups of group-rings of Galois groups, and in [ 3 ] Burns gave several conjectures (see Conjecture 3.1) about their values. In this paper I shall verify Burns' conjecture concerning the invariant $T\Omega^{\rm loc}( N/{\bf Q},1)$ for some families of quaternion extensions $N/{\bf Q}$ . Using the results of [ 9 ] I intend in a subsequent paper to verify Burns' conjecture for those families of quaternion fields which are not covered here.

Szemeredi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory [J. Komlos and M. Simonovits, Szemeredi's Regularity Lemma and its applications in graph theory, Combinatorics 2 (1996), 295-352]. Many of its applications are based on the following technical fact: If G is a k-partite graph with V(G) = ∪ki=1 Vi, |Vi| = n for all i ∈ [k], and all pairs {Vi, Vj}, 1 ≤ i < j ≤ k, are e-regular of density d, then G contains d??nk(1 + f(e)) cliques K(2)k, where f(e) → 0 as e → 0. The aim of this paper is to establish the analogous statement for 3-uniform hypergraphs. Our result, to which we refer as The Counting Lemma, together with Theorem 3.5 of P. Frankl and V. Rodl [Extremal problems on set systems, Random Structures Algorithms 20(2) (2002), 131-164), a Regularity Lemma for Hypergraphs, can be applied in various situations as Szemeredi's Regularity Lemma is for graphs. Some of these applications are discussed in previous papers, as well as in upcoming papers, of the authors and others.

The statement (and the proof) of Theorem 4.1.1 of the paper ‘Mackey formula in type A’ [Proc. London. Math. Soc. (3) 80 (2000) 545–574] is false. In this corrigendum we provide a correct statement (and a correct proof). As a consequence, we see that Corollary 4.1.2 of the paper holds. So all the other statements in the paper are correct (up to minor misprints…).2000 Mathematical Subject Classification: 20G05, 20G40.

Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].

Time-variantfilters based on Calderon and Gabor reproducingformulas are important tools in time­ frequencyanalysis.The paper studiesthe behaviorof the eigenvaluesof these filters.Optimal two-sided estimates of the number of eigenvaluescontainedin the interval (151,02), where 0 < 01 < 152 < 1, arc obtained.The estimatescoverlarge classesof localizationdomainsand generatingfunctions. 1. Introduction and statements of the results Calderon- Toeplitz and Gabor- Toeplitz operators arise naturally in two contexts: (i) Toephtz operators on Fock and Bergman spaces of holomorphic functions; (ii) time-variant filters based on Calderon and Gabor reproducing formulas. This paper is concerned with the eigenvalues of a subclass of Calderon- Toeplitz and Gabor- Toeplitz operators which have characteristic functions of bounded domains as symbols. Operators of this class are called time-frequency localiza­ tion operators. The basic idea of functional calculus is that the operators resemble the main algebraic features of their symbols. We consider symbols that are idem­ potent with respect to pointwise multiplication, so it is natural to expect that the corresponding operators are at least approximately idempotent. It is easy to verify that time-frequency localization operators are compact, self-adjoint and bounded by 1. In view of these facts and the above-mentioned correspondence principle, one is inclined to think that localization operators should resemble finite dimensional orthogonal projections. We show that this expectation is correct for Gabor- Toeplitz operators and that it is false for Calderon- Toeplitz operators. We identify the basic geometric features responsible for these two different behaviors. Our principal results are two-sided estimates of the number of eigenvalues inside the plunge region corresponding to 61, (52, where 0 < 61 < (52 < 1. The plunge region consists of the set of indices of the eigenvalues contained inside the open interval (61,62). The eigen­ val ues are ordered non-increasingly. Our work generalizes and improves previ ous results of Daubechies, Paul, Ramanathan and Topiwala [6, 8, 21].

In previous papers the authors showed that almost all d-regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001

The paper gives a formula for the probability that a randomly chosen elliptic curve over a finite field has a prime number of points. Two heuristic arguments in support of the formula are given as well as experimental evidence. The paper also gives a formula for the probability that a randomly chosen elliptic curve over a finite field has kq points where k is a small number and q is a prime.

In [6] S. Shelah showed that in the endomorphism semi-group of an infinitely generated algebra which is free in a variety one can interpret some set theory. It follows from his results that, for an algebra Fℵ which is free of infinite rank ℵ in a variety of algebras in a language L, if ℵ > |L|, then the first-order theory of the endomorphism semi-group of Fℵ, Th(End(Fℵ)), syntactically interprets Th(ℵ,L2), the second-order theory of the cardinal ℵ. This means that for any second-order sentence χ of empty language there exists χ*, a first-order sentence of semi-group language, such that for any infinite cardinal ℵ > |L|,formula hereIn his paper Shelah notes that it is natural to study a similar problem for automorphism groups instead of endomorphism semi-groups; a priori the expressive power of the first-order logic for automorphism groups is less than the one for endomorphism semi-groups. For instance, according to Shelah's results on permutation groups [4, 5], one cannot interpret set theory by means of first-order logic in the permutation group of an infinite set, the automorphism group of an algebra in empty language. On the other hand, one can do this in the endomorphism semi-group of such an algebra.In [7, 8] the author found a solution for the case of the variety of vector spaces over a fixed field. If V is a vector space of an infinite dimension ℵ over a division ring D, then the theory Th(ℵ, L2) is interpretable in the first-order theory of GL(V), the automorphism group of V. When a field D is countable and definable up to isomorphism by a second-order sentence, then the theories Th(GL(V)) and Th(ℵ, L2) are mutually syntactically interpretable. In the general case, the formulation is a bit more complicated.The main result of this paper states that a similar result holds for the variety of all groups.

A {\em convex corner} is a compact convex down-set of full dimension in . Convex corners arise in graph theory, for instance as stable set polytopes of graphs. They are also natural objects of study in geometry, as they correspond to 1-unconditional norms in an obvious way. In this paper, we study a parameter of convex corners, which we call the {\em content}, that is related to the volume. This parameter has appeared implicitly before: both in geometry, chiefly in a paper of Meyer ({\em Israel J.\ Math.} 55 (1986) 317--327) effectively using content to give a proof of Saint-Raymond's Inequality on the volume product of a convex corner, and in combinatorics, especially in a paper of Sidorenko ({\em Order} 8 (1991) 331--340) relating content to the number of linear extensions of a partial order. One of our main aims is to expose connections between work in these two areas. We prove many new results, giving in particular various generalizations of Saint-Raymond's Inequality. Content also behaves well under the operation of {\em pointwise product} of two convex corners; our results enable us to give counter-examples to two conjectures of Bollob\'as and Leader ({\em Oper.\ Theory Adv.\ Appl.} 77 (1995) 13--24) on pointwise products. 1991 Mathematics Subject Classification: 52C07, 51M25, 52B11, 05C60, 06A07.

In a paper of 1933, D. H. Lehmer continued Pierce's study of integral sequences associated to polynomials generalizing the Mersenne sequence. He developed divisibility criteria, and suggested that prime apparition in these sequences — or in closely related sequences — would be denser if the polynomials were close to cyclotomic, using a natural measure of closeness.We review briefly some of the main developments since Lehmer's paper, and report on further computational work on these sequences. In particular, we use Mossinghoff's collection of polynomials with smallest known measure to assemble evidence for the distribution of primes in these sequences predicted by standard heuristic arguments.The calculations lend weight to standard conjectures about Mersenne primes, and the use of polynomials with small measure permits much larger numbers of primes to be generated than in the Mersenne case.