Search

The feasible region Ω ind (F) of a graph F is the collection of points (x , y) in the unit square such that there exists a sequence of graphs whose edge densities approach x and whose induced F -densities approach y. A complete description of Ω ind (F) is not known for any F with at least four vertices that is not a clique or an independent set. The feasible region provides a lot of combinatorial information about F. For example, the supremum of y over all (x , y) ∈ Ω ind (F) is the inducibility of F and Ω ind (K r) yields the Kruskal-Katona and clique density theorems. We begin a systematic study of Ω ind (F) by proving some general statements about the shape of Ω ind (F) and giving results for some specific graphs F. Many of our theorems apply to the more general setting of quantum graphs. For example, we prove a bound for quantum graphs that generalizes an old result of Bollobás for the number of cliques in a graph with given edge density. We also consider the problems of determining Ω ind (F) when F = K r − , F is a star, or F is a complete bipartite graph. In the case of K r − our results sharpen those predicted by the edge-statistics conjecture of Alon et al. while also extending a theorem of Hirst for K 4 − that was proved using computer aided techniques and flag algebras. The case of the 4-cycle seems particularly interesting and we conjecture that Ω ind (C 4) is determined by the solution to the triangle density problem, which has been solved by Razborov. [ABSTRACT FROM AUTHOR]

We present a method which provides a unified framework for most stability theorems that have been proved in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph problems to the simpler question of checking that a hypergraph H with large minimum degree that omits the forbidden structures is vertex-extendable. This means that if v is a vertex of H and H − v is a subgraph of the extremal configuration(s), then H is also a subgraph of the extremal configuration(s). In many cases vertex-extendability is quite easy to verify. We illustrate our approach by giving new short proofs of hypergraph stability results of Pikhurko, Hefetz-Keevash, Brandt-Irwin-Jiang, Bene Watts-Norin-Yepremyan and others. Since our method always yields minimum degree stability, which is the strongest form of stability, in some of these cases our stability results are stronger than what was known earlier. Along the way, we clarify the different notions of stability that have been previously studied. [ABSTRACT FROM AUTHOR]

A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cgh's consisting of two distinct triangles. These were studied at length by Braß [6] (2004) and by Aronov, Dujmović, Morin, Ooms, and da Silveira [2] (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii [15] (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of n points in the plane. [ABSTRACT FROM AUTHOR]

Let F be a family of r -uniform hypergraphs. The feasible region Ω (F) of F is the set of points (x , y) in the unit square such that there exists a sequence of F -free r -uniform hypergraphs whose shadow density approaches x and whose edge density approaches y. The feasible region provides a lot of combinatorial information, for example, the supremum of y over all (x , y) ∈ Ω (F) is the Turán density π (F) , and Ω (∅) gives the Kruskal-Katona theorem. We undertake a systematic study of Ω (F) , and prove that Ω (F) is completely determined by a left-continuous almost everywhere differentiable function; and moreover, there exists an F for which this function is not continuous. We also extend some old related theorems. For example, we generalize a result of Fisher and Ryan to hypergraphs and extend a classical result of Bollobás by almost completely determining the feasible region for cancellative triple systems. [ABSTRACT FROM AUTHOR]

The Ramsey number r k ( s , n ) is the minimum N such that every red–blue coloring of the k -subsets of { 1 , … , N } contains a red set of size s or a blue set of size n , where a set is red (blue) if all of its k -subsets are red (blue). Let r k ( P s , n ) be the minimum N such that every red–blue coloring of the k -subsets of { 1 , … , N } results in a red ordered tight path with s vertices or a blue set of size n . The problem of estimating both r k ( s , n ) and r k ( P s , n ) for k = 2 goes back to the seminal work of Erdős and Szekeres from 1935, while the case k ≥ 3 was first investigated by Erdős and Rado in 1952. In this paper, we deduce the first quantitative relationship between multicolor variants of r k ( P s , n ) and r k ( n , n ) . This yields several consequences including the following: • We determine the correct tower growth rate for both r k ( s , n ) and r k ( P s , n ) for s ≥ k + 3 . The question of determining the tower growth rate of r k ( s , n ) for all s ≥ k + 1 was posed by Erdős and Hajnal in 1972 and this is almost settled here. • We show that determining the tower growth rate of r 4 ( P 5 , n ) is equivalent to determining the tower growth rate of r k ( n , n ) for all k ≥ 3 , which is a notorious conjecture of Erdős, Hajnal and Rado from 1965 that remains open. [ABSTRACT FROM AUTHOR]

The expansion G + of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a vertex disjoint from V ( G ) such that distinct edges are enlarged by distinct vertices. Let ex r ( n , F ) denote the maximum number of edges in an r -uniform hypergraph with n vertices not containing any copy of F . The authors [10] recently determined ex 3 ( n , G + ) when G is a path or cycle, thus settling conjectures of Füredi–Jiang [8] (for cycles) and Füredi–Jiang–Seiver [9] (for paths). Here we continue this project by determining the asymptotics for ex 3 ( n , G + ) when G is any fixed forest. This settles a conjecture of Füredi [7] . Using our methods, we also show that for any graph G , either ex 3 ( n , G + ) ≤ ( 1 2 + o ( 1 ) ) n 2 or ex 3 ( n , G + ) ≥ ( 1 + o ( 1 ) ) n 2 , thereby exhibiting a jump for the Turán number of expansions. [ABSTRACT FROM AUTHOR]

Let k ≥ 2 and F be a linear k -uniform hypergraph with v vertices. We prove that if n is sufficiently large and v | n , then every quasirandom k -uniform hypergraph on n vertices with constant edge density and minimum degree Ω ( n k − 1 ) admits a perfect F -packing. The case k = 2 follows immediately from the blowup lemma of Komlós, Sárközy, and Szemerédi. We also prove positive results for some nonlinear F but at the same time give counterexamples for rather simple F that are close to being linear. Finally, we address the case when the density tends to zero, and prove (in analogy with the graph case) that sparse quasirandom 3-uniform hypergraphs admit a perfect matching as long as their second largest eigenvalue is sufficiently smaller than the largest eigenvalue. [ABSTRACT FROM AUTHOR]

Fix an integer . A k-uniform hypergraph is simple if every two edges share at most one vertex. We prove that there is a constant c depending only on k such that every simple k-uniform hypergraph H with maximum degree Δ has chromatic number satisfying This implies a classical result of Ajtai, Komlós, Pintz, Spencer and Szemerédi and its strengthening due to Duke, Lefmann and Rödl. The result is sharp apart from the constant c. [ABSTRACT FROM AUTHOR]

Abstract: Let be fixed and n be sufficiently large. Suppose that is a collection of k-element subsets of an n-element set, and . Then contains d sets with union of size at most 2k and empty intersection. This extends the Erdős–Ko–Rado theorem and verifies a conjecture of the first author for large n. [Copyright &y& Elsevier]

Abstract: We prove that the maximum number of edges in a k-uniform hypergraph on n vertices containing no 2-regular subhypergraph is if is even and n is sufficiently large. Equality holds only if all edges contain a specific vertex v. For odd k we conjecture that this maximum is , with equality only for the hypergraph described above plus a maximum matching omitting v. [Copyright &y& Elsevier]

Abstract: Let the k-graph consist of k edges that pairwise intersect exactly in one vertex x, plus one more edge intersecting each of these edges in a vertex different from x. We prove that, for n sufficiently large, the maximum number of edges in an n-vertex k-graph containing no copy of is , which equals the number of edges in a complete k-partite k-graph with almost equal parts. This is the only extremal example. This result is a special case of our more general theorem that applies to a larger class of excluded configurations. [Copyright &y& Elsevier]

Abstract: The hypergraph product has vertex set , and edge set , where × denotes the usual Cartesian product of sets. We construct a hypergraph sequence for with and for all n. This disproves a conjecture of Berge and Simonovits [C. Berge, M. Simonovits, The coloring numbers of the direct product of two hypergraphs, in: Hypergraph Seminar, Proc. First Working Sem., Ohio State Univ., Columbus, OH, 1972; Dedicated to Arnold Ross, in: Lecture Notes in Math., vol. 411, Springer, Berlin, 1974, pp. 21–33]. On the other hand, we show that if G and H are hypergraphs with infinite chromatic number, then the chromatic number of is also infinite. We also provide a counterexample to a “dual” version of their conjecture, by constructing a graph sequence with and . The constant 1/2 cannot be replaced by a larger number. [Copyright &y& Elsevier]

Abstract: Fix . Let be the -uniform hypergraph obtained from the complete graph by enlarging each edge with a set of new vertices. Thus has vertices and edges. We prove that the maximum number of edges in an -vertex -uniform hypergraph containing no copy of isas . This is the first infinite family of irreducible -uniform hypergraphs for each odd whose Turán density is determined. Along the way, we give three proofs of a hypergraph generalization of Turán''s theorem. We also prove a stability theorem for hypergraphs, analogous to the Simonovits stability theorem for complete graphs. [Copyright &y& Elsevier]

Abstract: It is shown that every n vertex triple system with every pair of vertices lying in at least triples contains a copy of the Fano plane. The constant is sharp. This is the first triple system for which such a (nonzero) constant is determined. [Copyright &y& Elsevier]

A cancellative hypergraph has no three edges A,B,C with AΔB⊂C. We give a new short proof of an old result of Bollobás, which states that the maximum size of a cancellative triple system is achieved by the balanced complete tripartite 3-graph.One of the two forbidden subhypergraphs in a cancellative 3-graph is F5={abc,abd,cde}. For n⩾33 we show that the maximum number of triples on n vertices containing no copy of F5 is also achieved by the balanced complete tripartite 3-graph. This strengthens a theorem of Frankl and Füredi, who proved it for n⩾3000.For both extremal results, we show that a 3-graph with almost as many edges as the extremal example is approximately tripartite. These stability theorems are analogous to the Simonovits stability theorem for graphs. [Copyright &y& Elsevier]