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.     

Maximum Cliques of Hypergraphs and Polynomial Optimization

A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Buló and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local (global) minimizers of a homogeneous polynomial function of degree r and the maximal (maximum) cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Turán densities of complete non-uniform hypergraphs.     

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.     

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.     

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.     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

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.     

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.     

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.     

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.     

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.     

Nonlinear trigonometric approximations of multivariate function classes

Order-sharp estimates are established for the best N-term approximations of functions from Nikol’skii–Besov type classes B_pq^sm(T^k) with respect to the multiple trigonometric system T^(k) in the metric of L_r(T^k) for a number of relations between the parameters s, p, q, r, and m (s = (s₁,..., s_n) ∈ R₊ⁿ, 1 ≤ p, q, r ≤ ∞, m = (m₁,..., m_n) ∈ Nⁿ, k = m₁ +... + m_n). Constructive methods of nonlinear trigonometric approximation—variants of the so-called greedy algorithms—are used in the proofs of upper estimates.     

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.     

On the number of edges in a uniform hypergraph with a range of permitted intersections

The paper studies the quantity p(n, k, t ₁, t ₂) equal to the maximum number of edges in a k-uniform hypergraph with the property that the size of the intersection of any two edges lies in the interval [t ₁, t ₂]. Previously known upper and lower bounds are given. New bounds for p(n, k, t ₁, t ₂) are obtained, and the relationship between these bounds and known estimates is studied. For some parameter values, the exact values of p(n, k, t ₁, t ₂) are explicitly calculated.     

A tournament approach to pattern avoiding matrices

We consider the following Turán-type problem: given a fixed tournament H, what is the least integer t = t(n,H) so that adding t edges to any n-vertex tournament, results in a digraph containing a copy of H. Similarly, what is the least integer t = t(T _n ,H) so that adding t edges to the n-vertex transitive tournament, results in a digraph containing a copy of H. Besides proving several results on these problems, our main contributions are the following:

• Pach and Tardos conjectured that if M is an acyclic 0/1 matrix, then any n × n matrix with n(log n) ^O(1) entries equal to 1 contains the pattern M. We show that this conjecture is equivalent to the assertion that t(T _n ,H) = n(log n) ^O(1) if and only if H belongs to a certain (natural) family of tournaments.
• We propose an approach for determining if t(n,H) = n(log n) ^O(1). This approach combines expansion in sparse graphs, together with certain structural characterizations of H-free tournaments. Our result opens the door for using structural graph theoretic tools in order to settle the Pach–Tardos conjecture.

     

Dominant dimensions,derived equivalences and tilting modules

We show that for every ? > 0 there exist δ > 0 and n₀ ∈ ? such that every 3-uniform hypergraph on n ≥ n₀ vertices with the property that every k-vertex subset, where k ≥ δn, induces at least \(\left( {\frac{1}{2} + \varepsilon } \right)\left( {\begin{array}{*{20}c} k \\ 3 \\ \end{array} } \right)\) edges, contains K₄^? as a subgraph, where K₄^? is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erd?s and Sós. The constant 1/4 is the best possible.     

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.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

On Frankl and Füredi’s conjecture for 3-uniform hypergraphs

Frankl and Füredi in [1] conjectured that the r-graph with m edges formed by taking the first m sets in the colex ordering of N^(r) has the largest Lagrangian of all r-graphs with m edges. Denote this r-graph by C _r,m and the Lagrangian of a hypergraph by λ(G). In this paper, we first show that if \(\leqslant m \leqslant \left( {\begin{array}{*{20}{c}}t \\ 3 \end{array}} \right)\), G is a left-compressed 3-graph with m edges and on vertex set [t], the triple with minimum colex ordering in G ^c is (t ? 2 ? i)(t ? 2)t, then λ(G) ≤ λ(C _3,m ). As an implication, the conjecture of Frankl and Füredi is true for \(\left( {\begin{array}{*{20}{c}}t \\ 3\end{array}} \right) - 6 \leqslant m \leqslant \left( {\begin{array}{*{20}{c}}t \\ 3\end{array}} \right)\).     

Coloring number and on-line Ramsey theory for graphs and hypergraphs

Let c,s,t be positive integers. The (c,s,t)-Ramsey game is played by Builder and Painter. Play begins with an s-uniform hypergraph G ₀=(V,E ₀), where E ₀=Ø and V is determined by Builder. On the ith round Builder constructs a new edge e _i (distinct from previous edges) and sets G _i =(V,E _i ), where E _i =E _i?1∪{e _i }. Painter responds by coloring e _i with one of c colors. Builder wins if Painter eventually creates a monochromatic copy of K _s ^t , the complete s-uniform hypergraph on t vertices; otherwise Painter wins when she has colored all possible edges.We extend the definition of coloring number to hypergraphs so that χ(G)≤col(G) for any hypergraph G and then show that Builder can win (c,s,t)-Ramsey game while building a hypergraph with coloring number at most col(K _s ^t ). An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser. The (p,s,t)-survival game begins with an s-uniform hypergraph H ₀ = (V,Ø) with an arbitrary finite number of vertices and no edges. Let H _i?1=(V _i?1,E _i?1) be the hypergraph constructed in the first i ? 1 rounds. On the i-th round Presenter plays by presenting a p-subset P _i ?V _i?1 and Chooser responds by choosing an s-subset X _i ?P _i . The vertices in P _i ? X _i are discarded and the edge X _i added to E _i?1 to form E _i . Presenter wins the survival game if H _i contains a copy of K _s ^t for some i. We show that for positive integers p,s,t with s≤p, Presenter has a winning strategy.