Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

Dense 3-uniform hypergraphs containing a large clique

An r-uniform graph C is dense if and only if every proper subgraph G' of G satisfies λ(G') λ(G).,where λ(G) is the Lagrangian of a hypergraph G. In 1980's, Sidorenko showed that π(F), the Turán density of an γ-uniform hypergraph F is r! multiplying the supremum of the Lagrangians of all dense F-hom-free γ-uniform hypergraphs. This connection has been applied in the estimating Turán density of hypergraphs. When γ=2 the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph. However,when r ≥ 3, it becomes much harder to estimate the Lagrangians of γ-uniform hypergraphs and to characterize the structure of all dense γ-uniform graphs. The main goal of this note is to give some sufficient conditions for3-uniform graphs with given substructures to be dense. For example, if G is a 3-graph with vertex set [t] and m edges containing [t-1]~(3),then G is dense if and only if m≥{t-2 3)+(t-2 2)+1. We also give a sufficient condition on the number of edges for a 3-uniform hypergraph containing a large clique minus 1 or 2 edges to be dense.     

Connection between the clique number and the Lagrangian of 3-uniform hypergraphs

There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus (J Math 17:533–540, 1965). It would be useful in practice if similar results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus’ result to hypergraphs is false. Frankl and Füredi conjectured that the r-uniform hypergraph with m edges formed by taking the first m sets in the colex ordering of \({\mathbb N}^{(r)}\) has the largest Lagrangian of all r-uniform hypergraphs with m edges. For \(r=2\), Motzkin and Straus’ theorem confirms this conjecture. For \(r=3\), it is shown by Talbot that this conjecture is true when m is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for 3-uniform hypergraphs. As an application of this connection, we confirm that Frankl and Füredi’s conjecture holds for bigger ranges of m when \(r=3\). We also obtain two weaker versions of Turán type theorem for left-compressed 3-uniform hypergraphs.     

Connection Between Polynomial Optimization and Maximum Cliques of Non-Uniform Hypergraphs

In Motzkin and Straus (Canad. J. Math 498 17, 533540 1965) provided a connection between the order of a maximum clique in a graph G and the Lagrangian function of G. In Rota Bulò and Pelillo (Optim. Lett. 500 3, 287295 2009) extended the Motzkin-Straus result to r-uniform hypergraphs by establishing a one-to-one correspondence between local (global) minimizers of a family of homogeneous polynomial functions of degree r and the maximal (maximum) cliques of an r-uniform hypergraph. In this paper, we study similar optimization problems and obtain the connection to maximum cliques for {s, r}-hypergraphs and {p, s, r}-hypergraphs, which can be applied to obtain upper bounds on the Turán densities of the complete {s, r}-hypergraphs and {p, s, r}-hypergraphs.     

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.     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

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 a problem of Erdős and Moser

A set A of vertices in an r-uniform hypergraph \(\mathcal H\) is covered in \(\mathcal H\) if there is some vertex \(u\not \in A\) such that every edge of the form \(\{u\}\cup B\), \(B\in A^{(r-1)}\) is in \(\mathcal H\). Erd?s and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs.     

A Note on Generalized Lagrangians of Non-uniform Hypergraphs

Set \(A\subset {\mathbb N}\) is less than \(B\subset {\mathbb N}\) in the colex ordering if m a x(A△B)∈B. In 1980’s, Frankl and Füredi conjectured that the r-uniform graph with m edges consisting of the first m sets of \({\mathbb N}^{(r)}\) in the colex ordering has the largest Lagrangian among all r-uniform graphs with m edges. A result of Motzkin and Straus implies that this conjecture is true for r=2. This conjecture seems to be challenging even for r=3. For a hypergraph H=(V,E), the set T(H)={|e|:e∈E} is called the edge type of H. In this paper, we study non-uniform hypergraphs and define L(H) a generalized Lagrangian of a non-uniform hypergraph H in which edges of different types have different weights. We study the following two questions: 1. Let H be a hypergraph with m edges and edge type T. Let C _m,T denote the hypergraph with edge type T and m edges formed by taking the first m sets with cardinality in T in the colex ordering. Does L(H)≤L(C _m,T ) hold? If T={r}, then this question is the question by Frankl and Füredi. 2. Given a hypergraph H, find a minimum subhypergraph G of H such that L(G) = L(H). A result of Motzkin and Straus gave a complete answer to both questions if H is a graph. In this paper, we give a complete answer to both questions for {1,2}-hypergraphs. Regarding the first question, we give a result for {1,r ₁,r ₂,…,r _l }-hypergraph. We also show the connection between the generalized Lagrangian of {1,r ₁,r ₂,? ,r _l }-hypergraphs and {r ₁,r ₂,? ,r _l }-hypergraphs concerning the second question.     

Learning a hidden uniform hypergraph

Motivated by applications in genome sequencing, Grebinski and Kucherov (Discret Appl Math 88:147–165, 1998) studied the graph learning problem which is to identify a hidden graph drawn from a given class of graphs with vertex set \(\{1,2,\ldots ,n\}\) by edge-detecting queries. Each query tells whether a set of vertices induces any edge of the hidden graph or not. For the class of all hypergraphs whose edges have size at most r, Chodoriwsky and Moura (Theor Comput Sci 592:1–8, 2015) provided an adaptive algorithm that learns the class in \(O(m^r\log n)\) queries if the hidden graph has m edges. In this paper, we provide an adaptive algorithm that learns the class of all r-uniform hypergraphs in \(mr\log n+(6e)^rm^{\frac{r+1}{2}}\) queries if the hidden graph has m edges.     

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.     

On Jumping Densities of Hypergraphs

A number \({\alpha\in [0, 1)}\) is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family \({{\mathcal F}}\) of r-uniform graphs, if the Turán density of \({{\mathcal F}}\) is greater than α, then the Turán density of \({{\mathcal F}}\) is at least α + c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0, 1) is a jump for r = 2. Erd?s also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if \({c\cdot{\frac{r!}{r^r}}}\) is a non-jump for r ≥ 3, then for every p ≥ r, \({c\cdot{\frac{p!}{p^p}}}\) is a non-jump for p.     

Spectral radius of <Emphasis Type="Italic">r</Emphasis>-uniform supertrees with perfect matchings

supertree is a connected and acyclic hypergraph. The set of r-uniform supertrees with n vertices and the set of r-uniform supertrees with perfect matchings on rk vertices are denoted by T_n and T_r,k, respectively. H. Li, J. Shao, and L. Qi [J. Comb. Optim., 2016, 32(3): 741–764] proved that the hyperstar S_n,r attains uniquely the maximum spectral radius in T_n. Focusing on the spectral radius in T_r,k, this paper will give the maximum value in T_r,k and their corresponding supertree.     

A note on the Structure of Turán Densities of Hypergraphs

Let r ≥ 2 be an integer. A real number α ∈ [0, 1) is a jump for r if there exists c > 0 such that no number in (α, α + c) can be the Turán density of a family of r-uniform graphs. A result of Erd?s and Stone implies that every α ∈ [0, 1) is a jump for r = 2. Erd?s asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.     

On Substructure Densities of Hypergraphs

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n ₀ such that any r-uniform graph with n > n ₀ vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.     

A Comment on Ryser’s Conjecture for Intersecting Hypergraphs

Let \(\tau({\mathcal{H}})\) be the cover number and \(\nu({\mathcal{H}})\) be the matching number of a hypergraph \({\mathcal{H}}\). Ryser conjectured that every r-partite hypergraph \({\mathcal{H}}\) satisfies the inequality \(\tau({\mathcal{H}}) \leq (r-1) \nu ({\mathcal{H}})\). This conjecture is open for all r ≥ 4. For intersecting hypergraphs, namely those with \(\nu({\mathcal{H}}) = 1\), Ryser’s conjecture reduces to \(\tau({\mathcal{H}}) \leq r-1\). Even this conjecture is extremely difficult and is open for all r ≥ 6. For infinitely many r there are examples of intersecting r-partite hypergraphs with \(\tau({\mathcal{H}}) = r-1\), demonstrating the tightness of the conjecture for such r. However, all previously known constructions are not optimal as they use far too many edges. How sparse can an intersecting r-partite hypergraph be, given that its cover number is as large as possible, namely \(\tau({\mathcal{H}}) \ge r-1\)? In this paper we solve this question for r ≤ 5, give an almost optimal construction for r = 6, prove that any r-partite intersecting hypergraph with τ(H) ≥ r ? 1 must have at least \((3-\frac{1}{\sqrt{18}})r(1-o(1)) \approx 2.764r(1-o(1))\) edges, and conjecture that there exist constructions with Θ(r) edges.     

Uniform extensions of partial geometries

A geometry of rank 2 is an incidence system (P, \(\mathcal{B}\)), where P is a set of points and \(\mathcal{B}\) is a set of subsets from P, called blocks. Two points are called collinear if they lie in a common block. A pair (a, B) from (P, \(\mathcal{B}\)) is called a flag if its point belongs to the block, and an antiflag otherwise. A geometry is called φ-uniform (φ is a natural number) if for any antiflag (a, B) the number of points in the block B collinear to the point a equals 0 or φ, and strongly φ-uniform if this number equals φ. In this paper, we study φ-uniform extensions of partial geometries pG _α (s, t) with φ = s and strongly φ-uniform geometries with φ = s ? 1. In particular, the results on extensions of generalized quadrangles, obtained earlier by Cameron and Fisher, are extended to the case of partial geometries.     

Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles

We study the upper tail of the number of arithmetic progressions of a given length in a random subset of {1,..., n}, establishing exponential bounds which are best possible up to constant factors in the exponent. The proof also extends to Schur triples, and, more generally, to the number of edges in random induced subhypergraphs of ‘almost linear’ k-uniform hypergraphs.     

Largest <Emphasis Type="Italic">H</Emphasis>-eigenvalue of uniform <Emphasis Type="Italic">s</Emphasis>-hypertrees

The k-uniform s-hypertree G = (V,E) is an s-hypergraph, where 1 ≤ s ≤ k - 1; and there exists a host tree T with vertex set V such that each edge of G induces a connected subtree of T. In this paper, some properties of uniform s-hypertrees are establised, as well as the upper and lower bounds on the largest H-eigenvalue of the adjacency tensor of k-uniform s-hypertrees in terms of the maximal degree Δ. Moreover, we also show that the gap between the maximum and the minimum values of the largest H-eigenvalue of k-uniform s-hypertrees is just Θ(Δ ^s/k ).     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.