One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $n$vertex graph with more than $\frac{k1}{2}n$ edges contains any $k$edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $r$uniform hypergraph, i.e., a hypergraph where each edge contains $r$ vertices. A tight tree is an $r$uniform hypergraph such that there is an ordering $v_1,\ldots,v_n$ of its its vertices with the following property: the vertices $v_1,\ldots,v_r$ form an edge and for every $i>r$, there is a single edge $e$ containing the vertex $v_i$ and $r1$ of the vertices $v_1,\ldots,v_{i1}$, and $e\setminus\{v_i\}$ is a subset of one of the edges consisting only of vertices from $v_1,\ldots,v_{i1}$. The conjecture of Kalai asserts that every $n$vertex $r$uniform hypergraph with more than $\frac{k1}{r}\binom{n}{r1}$ edges contains every $k$edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $n$ for every $r$ and $k$.The articlemore »
A completion of the proof of the Edgestatistics Conjecture
Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number vertices as $H$; this quantity is known as the _inducibility_ of $H$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join each pair of vertices independently by an edge with probability $\binom{k}{2}^{1}$. The expected number of $k$vertex induced subgraphs with exactly one edge is $e^{1}+o(1)$. So, the inducibility of large graphs with a single edge is at least $e^{1}+o(1)$. This article establishes that this bound is more »
 Award ID(s):
 1855635
 Publication Date:
 NSFPAR ID:
 10178072
 Journal Name:
 Advances in Combinatorics
 Volume:
 1
 Issue:
 1
 Page Range or eLocationID:
 52 pages
 ISSN:
 25175599
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the problem of spaceefficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highlystudied problem of estimating the number of triangles in a graph stream. Our input is a kuniform hypergraph H with n vertices and m hyperedges, each hyperedge being a ksized subset of vertices. A ksimplex in H is a subhypergraph on k+1 vertices X such that all k+1 possible hyperedges among X exist in H. The goal is to process the hyperedges of H, which arrive in an arbitrary order as a data stream, and compute a good estimate of T_k(H), the number of ksimplices in H. We design a suite of algorithms for this problem. As with trianglecounting in graphs (which is the special case k = 2), sublinear space is achievable but only under a promise of the form T_k(H) ≥ T. Under such a promise, our algorithms use at most four passes and together imply a space bound of O(ε^{2} log δ^{1} polylog n ⋅ min{(m^{1+1/k})/T, m/(T^{2/(k+1)})}) for each fixed k ≥ 3, in order to guarantee an estimate within (1±ε)T_k(H) with probability ≥ 1δ. We also give a simpler 1pass algorithm thatmore »

We study the rank of a random n × m matrix An, m; k with entries from GF(2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix An, m; k forms the vertexedge incidence matrix of a kuniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let C2 be the number of vertices of the 2core of H, and  E (C2) the number of edges. Let m* be the value of m for which C2 = E(C2). Then w.h.p. for m < m* the rank of An, m; k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m – E(C2) + C2. In addition, assign i.i.d. U[0, 1] weights Xi, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X(S) = ∑j∊S Xj. Definemore »

Abstract Given two k graphs ( k uniform hypergraphs) F and H , a perfect F tiling (or F factor) in H is a set of vertexdisjoint copies of F that together cover the vertex set of H . For all complete k partite k graphs K , Mycroft proved a minimum codegree condition that guarantees a K factor in an n vertex k graph, which is tight up to an error term o ( n ). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are coprime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K (k) (1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.

Let C be a class of graphs closed under taking induced subgraphs. We say that C has the cliquestable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with P ≤ V (G) c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the cliquestable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the cliquestable set separation property.