Search

Given a fixed hypergraph H, let \operatorname {wsat}(n,H) denote the smallest number of edges in an n-vertex hypergraph G, with the property that one can sequentially add the edges missing from G, so that whenever an edge is added, a new copy of H is created. The study of \operatorname {wsat}(n,H) was introduced by Bollobás in 1968, and turned out to be one of the most influential topics in extremal combinatorics. While for most H very little is known regarding \operatorname {wsat}(n,H), Alon proved in 1985 that for every graph H there is a limiting constant C_H so that \operatorname {wsat}(n,H)=(C_H+o(1))n. Tuza conjectured in 1992 that Alon's theorem can be (appropriately) extended to arbitrary r-uniform hypergraphs. In this paper we prove this conjecture. [ABSTRACT FROM AUTHOR]

We show that there exist linear 3-uniform hypergraphs with n vertices and Ω (n2) edges which contain no copy of the 3 × 3 grid. This makes significant progress on a conjecture of Füredi and Ruszinkó. We also discuss connections to proving lower bounds for the (9,6) Brown-Erdős-Sós problem and to a problem of Solymosi and Solymosi. [ABSTRACT FROM AUTHOR]

The Erdős–Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph H , have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of r -uniform hypergraphs. A theorem of Rödl asserts that if an n -vertex graph is non-universal then it contains an almost homogeneous set (i.e. one with edge density either very close to 0 or 1) of size Ω (n). We prove that if a 3-uniform hypergraph is non-universal then it contains an almost homogeneous set of size Ω (log ⁡ n). An example of Rödl from 1986 shows that this bound is tight. Let R r (t) denote the size of the largest non-universal r -graph G so that neither G nor its complement contain a complete r -partite subgraph with parts of size t. We prove an Erdős–Hajnal-type stepping-up lemma, showing how to transform a lower bound for R r (t) into a lower bound for R r + 1 (t). As an application of this lemma, we improve a bound of Conlon–Fox–Sudakov by showing that R 3 (t) ≥ t Ω (t). [ABSTRACT FROM AUTHOR]

A well-known observation of Lovász is that if a hypergraph is not 2-colourable, then at least one pair of its edges intersect at a single vertex. In this short paper we consider the quantitative version of Lovász's criterion. That is, we ask how many pairs of edges intersecting at a single vertex should belong to a non-2-colourable n-uniform hypergraph. Our main result is an exact answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollobás's two families theorem with Pluhar's randomized colouring algorithm. [ABSTRACT FROM AUTHOR]

The hypergraph regularity lemma—the extension of Szemerédi's graph regularity lemma to the setting of k-uniform hypergraphs—is one of the most celebrated combinatorial results obtained in the past decade. By now there are several (very different) proofs of this lemma, obtained by Gowers, by Nagle–Rödl–Schacht–Skokan and by Tao. Unfortunately, what all these proofs have in common is that they yield regular partitions whose order is given by the k-th Ackermann function. We show that such Ackermann-type bounds are unavoidable for every k ≥ 2 , thus confirming a prediction of Tao. Prior to our work, the only result of this type was Gowers' famous lower bound for graph regularity. [ABSTRACT FROM AUTHOR]

Let K p 1 , … , p d d denote the complete d -uniform d -partite hypergraph with partition classes of sizes p 1 , … , p d . A hypergraph G ⊆ K n , … , n d is said to be weakly K p 1 , … , p d d -saturated if one can add the edges of K n , … , n d ∖ G in some order so that at each step a new copy of K p 1 , … , p d d is created. Let W n ( p 1 , … , p d ) denote the minimum number of edges in such a hypergraph. The problem of bounding W n ( p 1 , … , p d ) was introduced by Balogh, Bollobás, Morris and Riordan who determined it when each p i is either 1 or some fixed p . In this note we fully determine W n ( p 1 , … , p d ) . Our proof applies a reduction to a multi-partite version of the Two Families Theorem obtained by Alon. While the reduction is combinatorial, the main idea behind it is algebraic. [ABSTRACT FROM AUTHOR]

Let H be a k-uniform hypergraph whose vertices are the integers 1,...,N. We say that H contains a monotone path of length n if there are x1< x2…

Szemerédi's regularity lemma is a cornerstone result in extremal combinatorics. It (roughly) asserts that any dense graph is composed of a finite number of pseudorandom graphs. The regularity lemma has found many applications in theoretical computer science, and thus a lot of attention was given to designing algorithmic versions of this lemma. Our main results in this paper are the following: (i) We introduce a new approach to the problem of constructing regular partitions of graphs, which results in a surprisingly simple O(n) time algorithmic version of the regularity lemma, thus improving over the previous O(n2) time algorithms. Furthermore, unlike all the previous approaches for this problem (see [N. Alon and A. Naor, SIAM J. Comput., 35 (2006), pp. 787-803], [R. A. Duke, H. Lefmann, and V. Rödl, SIAM J. Comput., 24 (1995), pp. 598-620], [A. Frieze and R. Kannan, Electron. J. Combin., 6 (1999), article 17], [A. Frieze and R. Kannan, "The regularity lemma and approximation schemes for dense problems," in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 12-20], and [Y. Kohayakawa, V. Rödl, and L. Thoma, SIAM J. Comput., 32 (2003), pp. 1210-1235]), which only guaranteed to find tower-size partitions, our algorithm will find a small regular partition, if one exists in the graph. (ii) For any constant r ≥ 3 we give an O(n) time randomized algorithm for constructing regular partitions of r-uniform hypergraphs, thus improving the previous O(n2r-1) time (deterministic) algorithms [A. Czygrinow and V. Rödl, SIAM J. Comput., 30 (2000), pp. 1041-1066], [A. Frieze and R. Kannan, "The regularity lemma and approximation schemes for dense problems," in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 12-20]. These two results are obtained as an application of an efficient algorithm for approximating partition problems of hypergraphs which we obtain here: Given a (directed) hypergraph with bounded edge arities, a set of constraints on the set sizes and densities of a possible partition of its vertex set, and an approximation parameter, we provide in O(n) time a partition approximating the constraints if a partition satisfying them exists. We can also test in O(1) time for the existence of such a partition given the approximation parameter. This algorithm extends the result of Goldreich, Goldwasser, and Ron for graph partition problems [O. Goldreich, S. Goldwasser, and D. Ron, J. ACM, 45 (1998), pp. 653-750] and encompasses more recent hypergraph-related results such as the maximal constraint satisfaction approximation of [G. Andersson and L. Engebretsen, Random Structures Algorithms, 21 (2002), pp. 14-32]. [ABSTRACT FROM AUTHOR]

Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1,d]. We say that Φ is ∊-far from satisfiable, if one must remove at least ∊nk functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ∊-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/∊2, are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT.Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ∊-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ∊-far from satisfiable instances, in randomized constant time.From the above result we obtain as a special case, previous results of Alon and Krivelevich, and of Czumaj and Sohler, concerning testing of graphs and hypergraphs colorability. We also discuss the difference between testing with one-sided and two-sided error. [Copyright &y& Elsevier]

Let f (n , v , e) denote the maximum number of edges in a 3-uniform hypergraph not containing e edges spanned by at most v vertices. One of the most influential open problems in extremal combinatorics then asks, for a given number of edges e ≥ 3 , what is the smallest integer d = d (e) such that f (n , e + d , e) = o (n 2) ? This question has its origins in work of Brown, Erdős and Sós from the early 70's and the standard conjecture is that d (e) = 3 for every e ≥ 3. The state of the art result regarding this problem was obtained in 2004 by Sárközy and Selkow, who showed that f (n , e + 2 + ⌊ log 2 ⁡ e ⌋ , e) = o (n 2). The only improvement over this result was a recent breakthrough of Solymosi and Solymosi, who improved the bound for d (10) from 5 to 4. We obtain the first asymptotic improvement over the Sárközy–Selkow bound, showing that f (n , e + O (log ⁡ e / log ⁡ log ⁡ e) , e) = o (n 2). [ABSTRACT FROM AUTHOR]