The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

Inequalities for <Emphasis Type="Bold">cd</Emphasis>-Indices of Joins and Products of Polytopes

The cd-index is a polynomial which encodes the flag f-vector of a convex polytope. For polytopes U and V, we determine explicit recurrences for computing the cd-index of the free join and the cd-index of the Cartesian product U x V. As an application of these recurrences, we prove the inequality involving the cd-indices of three polytopes.     

Small Complete Arcs in Projective Planes

In the late 1950s, B. Segre introduced the fundamental notion of arcs and complete arcs [48,49]. An arc in a nite projective plane is a set of points with no three on a line and it is complete if cannot be extended without violating this property. Given a projective plane , determining , the size of its smallest complete arc, has been a major open question in finite geometry for several decades. Assume that has order q, it was shown by Lunelli and Sce [41], more than 40 years ago, that . Apart from this bound, practically nothing was known about , except for the case is the Galois plane. For this case, the best upper bound, prior to this paper, was O(q ^3/4) obtained by Sznyi using the properties of the Galois field GF(q).In this paper, we prove that for any projective plane of order q, where c is a universal constant. Together with Lunelli-Sces lower bound, our result determines up to a polylogarithmic factor. Our proof uses a probabilistic method known as the dynamic random construction or Rödls nibble. The proof also gives a quick randomized algorithm which produces a small complete arc with high probability.The key ingredient of our proof is a new concentration result, which applies for non-Lipschitz functions and is of independent interest.* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.Part of this work was done at AT&T Bell Labs and Microsoft Research     

A Littlewood-Paley type inequality

In this note we prove the following theorem: Let u be a harmonic function in the unit ball and . Then there is a constant C = C(p, n) such that

An Upper Bound for the Cardinality of an <Emphasis Type="Italic">s</Emphasis>-Distance Set in Euclidean Space

In this paper we show that if X is an s-distance set in ^m and X is on p concentric spheres then Moreover if X is antipodal, then .     

Sharp Estimates for Deviations of Linear Approximation Methods for Periodic Functions by Linear Combinations of Moduli of Continuity of Different Order

Estimates for deviations are established for a large class of linear methods of approximation of periodic functions by linear combinations of moduli of continuity of different orders. These estimates are sharp in the sense of constants in the uniform and integral metrics. In particular, the following assertion concerning approximation by splines is proved: Suppose that is odd, . Then

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

Some Remarks on the Simultaneous Chromatic Number

We present several partial results, variants, and consistency results concerning the following (as yet unsolved) conjecture. If X is a graph on the ground set V with then X has an edge coloring F with colors such that if V is decomposed into parts then there is one in which F assumes all values.Due to some unfortunate misunderstandings, this paper appeared much later than we expected.* Research partially supported by NSF grants DMS-9704477 and DMS-0072560. Research partially supported by Hungarian National Research Grant T 032455.     

Linear Codes and Character Sums

Let V be an rn-dimensional linear subspace of . Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and distance d.) We settle two extremal problems on such spaces.First, we prove a (weak form) of a conjecture by Kalai and Linial and show that the fraction of vectors in V with weight d is exponentially small. Specifically, in the interesting case of a small r, this fraction does not exceed .We also answer a question of Ben-Or and show that if , then for every k, at most vectors of V have weight k.Our work draws on a simple connection between extremal properties of linear subspaces of and the distribution of values in short sums of -characters.* Supported in part by grants from the Israeli Academy of Sciences and the Binational Science Foundation Israel-USA. This work was done while the author was a student in the Hebrew University of Jerusalem, Israel.     

Semisimplicity of Some Class of Operator Algebras on Banach Space

Let G be a locally compact abelian group and let be a representation of G by means of isometries on a Banach space. We define W_T as the closure with respect to the weak operator topology of the set where is the Fourier transform of f ∈L¹(G) with respect to the group T. Then W_T is a commutative Banach algebra. In this paper we study semisimlicity problem for such algebras. The main result is that if the Arveson spectrum sp(T) of T is scattered (i.e. it does not contain a nonempty perfect subset) then the algebra W_T is semisimple. Some related problems are also discussed.     

Ultraproducts of real interpolation spaces between L p -spaces

Let , be a family of compatible couples of L^p-spaces. We show that, given a countably incomplete ultrafilter in , the ultraproduct of interpolation spaces defined by the real method is isomorphic to the direct sum of an interpolation space of type , an intermediate K?the space between and being a purely atomic measure space, and a K?the function space K(Ω₃) defined on some purely non atomic measure space (Ω₃, ν₃) in such a way that Ω₂ ∪ Ω₃ ≠∅. The research of first and third authors is partially supported by the MEC and FEDER project MTM2004-02262 and AVCIT group 03/050.     

Lifts, Discrepancy and Nearly Optimal Spectral Gap*

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l₁ norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}ⁿ with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.     

A Sharp Bound for the Number of Sets that Pairwise Intersect at <Emphasis Type="Italic">k</Emphasis> Positive Values

In this paper we prove that if is a set of k positive integers and {A ₁, ..., A _m } is a family of subsets of an n-element set satisfying , for all 1 i < j m, then . The case k = 1 was proven 50 years ago by Majumdar.     

On Shadows Of Intersecting Families

The shadow minimization problem for t-intersecting systems of finite sets is considered. Let be a family of k-subsets of . The -shadow of is the set of all (k-)-subsets contained in the members of . Let be a t-intersecting family (any two members have at least t elements in common) with . Given k,t,m the problem is to minimize (over all choices of ). In this paper we solve this problem when m is big enough.     

Regularity of Weak Solutions of Nonlinear Equations with Discontinuous Coefficients

In this paper, we prove that the weak solutions u∈Wloc^1, p （Ω） （1 〈p〈∞） of the following equation with vanishing mean oscillation coefficients A（x）： -div[（A（x）△↓u·△↓u）p-2/2 A（x）△↓u＋│F（x）│^p-2 F（x）]=B（x, u, △↓u）, belong to Wloc^1, q （Ω）（A↓q∈（p, ∞）, provided F ∈ Lloc^q（Ω） and B（x, u, h） satisfies proper growth conditions where Ω ∪→R^N（N≥2） is a bounded open set, A（x）=（A^ij（x）） N×N is a symmetric matrix function.     

Semi-Fredholm Spectrum and Weyl＇s Theorem for Operator Matrices

When A ∈ B（H） and B ∈ B（K） are given, we denote by Mc an operator acting on the Hilbert space HΘ K of the form Me = （ A0 CB）. In this paper, first we give the necessary and sufficient condition for Mc to be an upper semi-Fredholm （lower semi-Fredholm, or Fredholm） operator for some C ∈B（K,H）. In addition, let σSF＋（A） = {λ ∈ C ： A-λI is not an upper semi-Fredholm operator} bc the upper semi-Fredholm spectrum of A ∈ B（H） and let σrsF- （A） = {λ∈ C ： A-λI is not a lower semi-Fredholm operator} be the lower semi Fredholm spectrum of A. We show that the passage from σSF±（A） U σSF±（B） to σSF±（Mc） is accomplished by removing certain open subsets of σSF-（A） ∩σSF＋ （B） from the former, that is, there is an equality σSF±（A） ∪σSF± （B） = σSF± （Mc） ∪＆ where L is the union of certain of the holes in σSF±（Mc） which ilappen to be subsets of σSF- （A） A σSF＋ （B）. Weyl＇s theorem and Browder＇s theorem are liable to fail for 2 × 2 operator matrices. In this paper, we also explore how Weyl＇s theorem, Browder＇s theorem, a-Weyl＇s theorem and a-Browder＇s theorem survive for 2 × 2 upper triangular operator matrices on the Hilbert space.     

For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

An Elementary Approach to an Eigenvalue Estimate for Matrices

A celebrated result of Johnson, Maurey, König and Retherford from 1977 states that for every complex matrix satisfies the following eigenvalue estimate:

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.     

On the Order of Magnitude of the Divisor Function

Let D be an increasing sequence of positive integers, and consider the divisor functions： d（n, D） =∑d｜n,d∈D,d≤√n1, d2（n,D）=∑[d,δ]｜n,d,δ∈D,[d,δ]≤√n1, where [d,δ]=1.c.m.（d,δ）. A probabilistic argument is introduced to evaluate the series ∑n=1^∞and（n,D） and ∑n=1^∞and2（n,D）.