 Award ID(s):
 1855635
 NSFPAR ID:
 10178072
 Date Published:
 Journal Name:
 Advances in Combinatorics
 Volume:
 1
 Issue:
 1
 ISSN:
 25175599
 Page Range / eLocation ID:
 52 pages
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $r$tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous ErdősGallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first nontrivial upper bound valid for all $r$ and $k$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.more » « less

Abstract A graph is ‐
free if it has no induced subgraph isomorphic to , and G  denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:For every graph , there exists such that in every ‐free graph with 
This is equivalent to:G  there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.
The sparse linear conjecture holds for all almost‐bipartite graphs .
For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.
For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.

Abstract Given a
k ‐vertex graphH and an integern , what are then ‐vertex graphs with the maximum number of induced copies ofH ? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction ofk ‐vertex subsets of ann ‐vertex graph that induce a copy ofH . Huang, Lee, and the first author proved that for a randomk ‐vertex graphH , almost surely then ‐vertex graphs maximizing the number of induced copies ofH are the balanced iterated blow‐ups ofH . In this article, we consider the case where the graphH is obtained by deleting a small number of vertices from a random Cayley graphof an abelian group. We prove that in this case, almost surely all n ‐vertex graphs maximizing the number of induced copies ofH are balanced iterated blow‐ups of. 
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 that achieves O(ε^{2} log δ^{1} log n⋅ (m/T) (Δ_E + Δ_V^{11/k})) space, where Δ_E (respectively, Δ_V) denotes the maximum number of ksimplices that share a hyperedge (respectively, a vertex), which generalizes a previous result for the k = 2 case. We complement these algorithmic results with space lower bounds of the form Ω(ε^{2}), Ω(m^{1+1/k}/T), Ω(m/T^{11/k}) and Ω(mΔ_V^{1/k}/T) for multipass algorithms and Ω(mΔ_E/T) for 1pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs.more » « less

A _theta_ is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$_free_ if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)free graph $G$ has treewidth at most $c\log (V(G))$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $V(G)$ for every graph $G$ excluding the socalled _threepathconfigurations_ as well as a fixed complete graph. It follows that several NPhard problems such as Stable Set, Vertex Cover, Dominating Set and $k$Coloring (for fixed $k$) admit polynomial time algorithms in graphs excluding the threepathconfigurations and a fixed complete graph.more » « less