The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

A Neighborhood Condition for Graphs to Have [a, b]-Factors II

 Let a, b, m, and t be integers such that 1≤a<b and 1≤t≤⌉(b−m+1)/a⌉. Suppose that G is a graph of order |G| and H is any subgraph of G with the size |E(H)|=m. Then we prove that G has an [a,b]-factor containing all the edges of H if the minimum degree is at least a, |G|>((a+b)(t(a+b−1)−1)+2m)/b, and |N _G (x ₁)∪⋯ ∪N _G (x _t )|≥(a|G|+2m)/(a+b) for every independent set {x ₁,…,x _t }⊆V(G). This result is best possible in some sense and it is an extension of the result of H. Matsuda (A neighborhood condition for graphs to have [a,b]-factors, Discrete Mathematics 224 (2000) 289–292). Received: October, 2001 Final version received: September 17, 2002 RID="*" ID="*" This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 13740084, 2001     

On the 3-Torsion Part of the Homology of the Chessboard Complex

Let 1 ≤ m ≤ n. We prove various results about the chessboard complex M _m,n , which is the simplicial complex of matchings in the complete bipartite graph K _m,n . First, we demonstrate that there is nonvanishing 3-torsion in [(H)\tilde]_d(\sf M_m,n; \mathbb Z){{\tilde{H}_d({\sf M}_{m,n}; {\mathbb Z})}} whenever \fracm+n-43 ￡ d ￡ m-4{{\frac{m+n-4}{3}\leq d \leq m-4}} and whenever 6 ≤ m < n and d = m − 3. Combining this result with theorems due to Friedman and Hanlon and to Shareshian and Wachs, we characterize all triples (m, n, d ) satisfying [(H)\tilde]_d (\sf M_m,n; \mathbb Z) 1 0{{\tilde{H}_d \left({\sf M}_{m,n}; {\mathbb Z}\right) \neq 0}}. Second, for each k ≥ 0, we show that there is a polynomial f _k (a, b) of degree 3k such that the dimension of [(H)\tilde]_k+a+2b-2 (\sf M_{k+a+3b-1,k+2a+3b-1}; \mathbb Z₃){{\tilde{H}_{k+a+2b-2}}\,\left({{\sf M}_{k+a+3b-1,k+2a+3b-1}}; \mathbb Z_{3}\right)}, viewed as a vector space over \mathbbZ₃{\mathbb{Z}_3}, is at most f _k (a, b) for all a ≥ 0 and b ≥ k + 2. Third, we give a computer-free proof that [(H)\tilde]₂ (\sf M_5,5; \mathbb Z) @ \mathbb Z₃{{\tilde{H}_2 ({\sf M}_{5,5}; \mathbb {Z})\cong \mathbb Z_{3}}}. Several proofs are based on a new long exact sequence relating the homology of a certain subcomplex of M _m,n to the homology of M _m-2,n-1 and M _m-2,n-3.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Coxeter group actions on <Subscript>4</Subscript><Emphasis Type="Italic">F</Emphasis><Subscript>3</Subscript>(1) hypergeometric series

In this paper we investigate a certain linear combination K([(x)\vec])=K(a;b,c,d;e,f,g)K(\vec{x})=K(a;b,c,d;e,f,g) of two Saalschutzian hypergeometric series of type ₄ F ₃(1). We first show that K([(x)\vec])K(\vec{x}) is invariant under the action of a certain matrix group G _K , isomorphic to the symmetric group S ₆, acting on the affine hyperplane V={(a,b,c,d,e,f,g)∈ℂ⁷:e+f+g−a−b−c−d=1}. We further develop an algebra of three-term relations for K(a;b,c,d;e,f,g). We show that, for any three elements μ ₁,μ ₂,μ ₃ of a certain matrix group M _K , isomorphic to the Coxeter group W(D ₆) (of order 23040) and containing the above group G _K , there is a relation among K(m₁[(x)\vec])K(\mu_{1}\vec{x}), K(m₂[(x)\vec])K(\mu_{2}\vec{x}), and K(m₃[(x)\vec])K(\mu_{3}\vec{x}), provided that no two of the μ _j ’s are in the same right coset of G _K in M _K . The coefficients in these three-term relations are seen to be rational combinations of gamma and sine functions in a,b,c,d,e,f,g.     

Thed-step conjecture for polyhedra of dimensiond<6

Two functions Δ and Δ _b , of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ(d, n) is the maximum diameter of convex polyhedra of dimensiond withn faces of dimensiond−1; similarly, Δ _b (d,n) is the maximum diameter of bounded polyhedra of dimensiond withn faces of dimensiond−1. The diameter of a polyhedronP is the smallest integerl such that any two vertices ofP can be joined by a path ofl or fewer edges ofP. It is shown that the boundedd-step conjecture, i.e. Δ _b (d,2d)=d, is true ford≤5. It is also shown that the generald-step conjecture, i.e. Δ(d, 2d)≤d, of significance in linear programming, is false ford≥4. A number of other specific values and bounds for Δ and Δ _b are presented. This revised version was published online in November 2006 with corrections to the Cover Date.     

Sets of Periods for Expanding Maps on Flat Manifolds

 It is proven that the sets of periods for expanding maps on n-dimensional flat manifolds are uniformly cofinite, i.e. there is a positive integer m ₀, which depends only on n, such that for any integer , for any n-dimensional flat manifold ℳ and for any expanding map F on ℳ, there exists a periodic point of F whose least period is exactly m.     

Q 2-free Families in the Boolean Lattice

For a family F{{\cal F}} of subsets of [n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that F{{\cal F}} is P-free if it does not contain a subposet isomorphic to P. Let ex(n, P) be the largest size of a P-free family of subsets of [n]. Let Q ₂ be the poset with distinct elements a, b, c, d, a < b,c < d; i.e., the 2-dimensional Boolean lattice. We show that 2N − o(N) ≤ ex(n, Q ₂) ≤ 2.283261N + o(N), where N = \binomn?n/2 ?N = \binom{n}{\lfloor n/2 \rfloor}. We also prove that the largest Q ₂-free family of subsets of [n] having at most three different sizes has at most 2.20711N members.     

Triangle-free distance-regular graphs

Let Γ denote a distance-regular graph with diameter d≥3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Γ such that ∂(x,y)=∂(z,w)=1, ∂(x,z)=3, and ∂(x,w)=∂(y,w)=∂(y,z)=2, where ∂ denotes the path-length distance function. Assume that Γ has intersection numbers a ₁=0 and a ₂≠0. We prove that the following (i) and (ii) are equivalent. (i) Γ is Q-polynomial and contains no parallelograms of length 3; (ii) Γ has classical parameters (d,b,α,β) with b<−1. Furthermore, suppose that (i) and (ii) hold. We show that each of b(b+1)²(b+2)/c ₂, (b−2)(b−1)b(b+1)/(2+2b−c ₂) is an integer and that c ₂≤b(b+1). This upper bound for c ₂ is optimal, since the Hermitian forms graph Her₂(d) is a triangle-free distance-regular graph that satisfies c ₂=b(b+1). Work partially supported by the National Science Council of Taiwan, R.O.C.     

Sets of Periods for Expanding Maps on Flat Manifolds

 It is proven that the sets of periods for expanding maps on n-dimensional flat manifolds are uniformly cofinite, i.e. there is a positive integer m ₀, which depends only on n, such that for any integer , for any n-dimensional flat manifold ℳ and for any expanding map F on ℳ, there exists a periodic point of F whose least period is exactly m. (Received 10 April 1998; in revised form 20 January 1999)     

Reciprocal polynomials with all zeros on the unit circle

Let f(x)=a _d x ^d +a _d−1 x ^d−1+⋅⋅⋅+a ₀∈ℝ[x] be a reciprocal polynomial of degree d. We prove that if the coefficient vector (a _d ,a _d−1,…,a ₀) or (a _d−1,a _d−2,…,a ₁) is close enough, in the l ¹-distance, to the constant vector (b,b,…,b)∈ℝ ^d+1 or ℝ ^d−1, then all of its zeros have moduli 1.     

Degree Sequences and Chromatic Numbers of Graphs

 We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values χ(G) of the function chromatic number completely cover a line segment [a,b] of positive integers. Thus for an arbitrary graphical sequence d, two invariants minχ(d):=a and maxχ(d):=b naturally arise. For a regular graphical sequence d=r ⁿ :=(r,r,…,r) where r is the degree and n is the number of vertices, the exact values of a and b are found in all situations, except the case where n and r are both even and n<2r. Received: September 16, 2000 Final version received: December 13, 2001 Acknowledgments. We would like to thank Professor Tommy R. Jensen for his useful comment and editing thorough the paper.     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

Discretization of Compact Riemannian Manifolds Applied to the Spectrum of Laplacian

For κ ⩾ 0 and r₀ > 0 let ℳ(n, κ, r₀) be the set of all connected, compact n-dimensional Riemannian manifolds (Mⁿ, g) with Ricci (M, g) ⩾ −(n−1) κ g and Inj (M) ⩾ r₀. We study the relation between the kth eigenvalue λ_k(M) of the Laplacian associated to (Mⁿ,g), Δ = −div(grad), and the kth eigenvalue λ_k(X) of a combinatorial Laplacian associated to a discretization X of M. We show that there exist constants c, C > 0 (depending only on n, κ and r₀) such that for all M ∈ ℳ(n, κ, r₀) and X a discretization of for all k < |X|. Then, we obtain the same kind of result for two compact manifolds M and N ∈ ℳ(n, κ, r₀) such that the Gromov–Hausdorff distance between M and N is smaller than some η > 0. We show that there exist constants c, C > 0 depending on η, n, κ and r₀ such that for all . Mathematics Subject Classification (2000): 58J50, 53C20 Supported by Swiss National Science Foundation, grant No. 20-101 469     

On the Hamilton-Waterloo Problem

 The Hamilton-Waterloo problem asks for a 2-factorisation of K _v in which r of the 2-factors consist of cycles of lengths a ₁,a ₂,…,a _t and the remaining s 2-factors consist of cycles of lengths b ₁,b ₂,…,b _u (where necessarily ∑ _i=1 ^t a _i =∑ _j=1 ^u b _j =v). In this paper we consider the Hamilton-Waterloo problem in the case a _i =m, 1≤i≤t and b _j =n, 1≤j≤u. We obtain some general constructions, and apply these to obtain results for (m,n)∈{(4,6),(4,8),(4,16),(8,16),(3,5),(3,15),(5,15)}. Received: July 5, 2000     

An Extremal Problem on Degree Sequences of Graphs

 Let G=(I _n ,E) be the graph of the n-dimensional cube. Namely, I _n ={0,1} ⁿ and [x,y]∈E whenever ||x−y||₁=1. For A⊆I _n and x∈A define h _A (x) =#{y∈I _n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I _n of size 2 ⁿ⁻¹ we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences     

Invariant means

Let m and M be symmetric means in two and three variables, respectively. We say that M is type 1 invariant with respect to m if M(m(a,c),m(a,b),m(b,c))≡M(a,b,c). If m is strict and isotone, then we show that there exists a unique M which is type 1 invariant with respect to m. In particular, we discuss the invariant logarithmic mean L₃, which is type 1 invariant with respect to L(a,b)=(b−a)/(logb−loga). We say that M is type 2 invariant with respect to m if M(a,b,m(a,b))≡m(a,b). We also prove existence and uniqueness results for type 2 invariance, given the mean M(a,b,c). The arithmetic, geometric, and harmonic means in two and three variables satisfy both type 1 and type 2 invariance. There are means m and M such that M is type 2 invariant with respect to m, but not type 1 invariant with respect to m (for example, the Lehmer means). L₃ is type 1 invariant with respect to L, but not type 2 invariant with respect to L.     

Near-interpolation

Summary.  A parametric curve fL ₂ ^(m) ([a,b]ℝ ^d ) is a ``near-interpolant' to prescribed data z <sub>ij</sub> ℝ <sup>d</sup> at data sites t <sub>i</sub> [a,b] within tolerances 0<ɛ <sub>ij</sub> ≤∞ if |f <sup>(j−1)</sup> (t <sub>i</sub> )−z <sub>ij</sub> |≤ɛ <sub>ij</sub> for i=1:n and j=1:m, and a ``best near-interpolant' if it also minimizes ∫ _a ^b |f ^(m) |². In this paper optimality conditions are derived for these best near-interpolants. Based on these conditions it is shown that the near-interpolants are actually smoothing splines with weights that appear as Lagrange multipliers corresponding to the constraints. The optimality conditions are applied to the computation of near-interpolants in the last sections of the paper. Received September 4, 2001 / Revised version received July 22, 2002 / Published online October 29, 2002 Mathematics Subject Classification (1991): 41A05, 41A15, 41A29     

Transcendence of Certain Reciprocal Sums of Linear Recurrences

 Suppose that {R _n } _n ⩾ 0 is a sequence of integers satisfying a binary linear recurrence relation with suitable conditions. We prove the transcendency of the numbers