Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

Decomposition of large uniform hypergraphs

We determine a minimum cardinality family _{n, k} (resp. _{n, k} ) ofn-uniform,k-edge hypergraphs satisfying the following property: all, except for finitely many,n-uniform hypergraphs satisfying the divisibility condition have an _{n, k} -decomposition (resp. vertex _{n, k} -decomposition).     

Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-uniform k-partite hypergraphs.     

A variant of the hypergraph removal lemma

Recent work of Gowers [T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299-345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275-291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes.     

A Solution to a Problem of Jacobson,Kézdy and Lehel

We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k²–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85)     

Perfect matchings in uniform hypergraphs with large minimum degree

A perfect matching in a k-uniform hypergraph on n vertices, n divisible by k, is a set of n/k disjoint edges. In this paper we give a sufficient condition for the existence of a perfect matching in terms of a variant of the minimum degree. We prove that for every k≥3 and sufficiently large n, a perfect matching exists in every n-vertex k-uniform hypergraph in which each set of k−1 vertices is contained in n/2+Ω(logn) edges. Owing to a construction in [D. Kühn, D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (1) (2006) 269–280], this is nearly optimal. For almost perfect and fractional perfect matchings we show that analogous thresholds are close to n/k rather than n/2.     

A generalization of the Motzkin–Straus theorem to hypergraphs

In 1965, Motzkin and Straus established a remarkable connection between the global maxima of the Lagrangian of a graph G over the standard simplex and the clique number of G. In this paper, we provide a generalization of the Motzkin–Straus theorem to k-uniform hypergraphs (k-graphs). Specifically, given a k-graph G, we exhibit a family of (parameterized) homogeneous polynomials whose local (global) minimizers are shown to be in one-to-one correspondence with maximal (maximum) cliques of G.     

3-uniform hypergraphs avoiding a given odd cycle

We give upper bounds for the size of 3-uniform hypergraphs avoiding a given odd cycle using the definition of a cycle due to Berge. In particular, we show that a 3-uniform hypergraph containing no cycle of length 2k+1 has less than 4k ⁴ n ^1+1/k +O(n) edges. Constructions show that these bounds are best possible (up to constant factor) for k=1,2,3, 5.     

Embeddings and Ramsey numbers of sparse <Emphasis Type="Italic">κ</Emphasis>-uniform hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [3] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [6,23] the same result was proved for 3-uniform hypergraphs. Here we extend this result to κ-uniform hypergraphs for any integer κ ≥ 3. As in the 3-uniform case, the main new tool which we prove and use is an embedding lemma for κ-uniform hypergraphs of bounded maximum degree into suitable κ-uniform ‘quasi-random’ hypergraphs.     

On decompositions of complete hypergraphs

We study the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edges of the complete r-uniform hypergraph on n vertices and we improve previous results of Alon.     

Generalisations of Hypomorphisms and Reconstruction of Hypergraphs

We define certain generalisations of hypergraph hypomorphisms, which we call k-morphisms, \((k,n-k)\)-hypomorphisms, partial \((k,n-k)\)-hypomorphisms. They are special bijections between collections of k-subsets of vertex sets of hypergraphs. We show that these mappings lead to alternative representations of the automorphism groups of r-uniform hypergraphs and vertex stabilisers of graphs. We also use them to show that almost every r-uniform hypergraph is reconstructible and \((k,n-k)\)-reconstructible. As a consequence we also obtain the result that almost every r-uniform hypergraph is asymmetric.     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Ordering uniform supertrees by their spectral radii

A supertree is a connected and acyclic hypergraph. For a hypergraph H, the maximal modulus of the eigenvalues of its adjacency tensor is called the spectral radius of H. By applying the operation of moving edges on hypergraphs and the weighted incidence matrix method, we determine the ninth and the tenth k-uniform supertrees with the largest spectral radii among all k-uniform supertrees on n vertices, which extends the known result.     

Series-parallel chromatic hypergraphs

In this paper two-terminal series-parallel chromatic hypergraphs are introduced and for this class of hypergraphs it is shown that the chromatic polynomial can be computed with polynomial complexity. It is also proved that h-uniform multibridge hypergraphs θ(h;a₁,a₂,…,a_k) are chromatically unique for h≥3 if and only if h=3 and a₁=a₂=?=a_k=1, i.e., when they are sunflower hypergraphs having a core of cardinality 2 and all petals being singletons.     

Linear CNF formulas and satisfiability

In this paper, we study linear CNF formulas generalizing linear hypergraphs under combinatorial and complexity theoretical aspects w.r.t. SAT. We establish NP-completeness of SAT for the unrestricted linear formula class, and we show the equivalence of NP-completeness of restricted uniform linear formula classes w.r.t. SAT and the existence of unsatisfiable uniform linear witness formulas. On that basis we prove NP-completeness of SAT for uniform linear classes in a resolution-based manner by constructing large-sized formulas. Interested in small witness formulas, we exhibit some combinatorial features of linear hypergraphs closely related to latin squares and finite projective planes helping to construct rather dense, and significantly smaller unsatisfiable k-uniform linear formulas, at least for the cases k=3,4.     

Enumeration of Maximum Acyclic Hypergraphs

Abstract Acyclic hypergraphs are analogues of forests in graphs.They are very useful in the design ofdatabases. In this article,the maximum size of an acvclic hypergraph is determined and the number of maximumγ-uniform acyclic hypergraphs of order n is shown to be (_(r-1)~n)(n(r-1)-r~2 2r)~(n-r-1).     

Hypergraphs with independent neighborhoods

For each k ≥ 2, let ρ _k ∈ (0, 1) be the largest number such that there exist k-uniform hypergraphs on n vertices with independent neighborhoods and (ρ _k + o(1))( _k ⁿ ) edges as n → ∞. We prove that ρ _k = 1 − 2logk/k + Θ(log log k/k) as k → ∞. This disproves a conjecture of Füredi and the last two authors.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following:

We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Füredi, Kahn and Seymour, showing that the integrality gap is exactly ${k-1+\frac{1}{k}}$ for k-uniform hypergraphs, and is exactly k ? 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems.

We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k ? 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most ${\frac{k+1}{2}}$ for k-uniform hypergraphs. The construction uses a result in extremal combinatorics.

We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovász ${\vartheta}$ -function provides an SDP relaxation with integrality gap at most ${\frac{k+1}{2}}$ . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.