More Like this

1. Tight paths in convex geometric hypergraphs

   https://doi.org/10.19086/aic.12044  

   Mubayi, Dhruv ; Füredi, Zoltán ; Verstraëte, Jacques ; Kostochka, Alexandr ; Jiang, Tao ( February 2020 , Advances in Combinatorics)

   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{k-1}{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 $r-1$ of the vertices $v_1,\ldots,v_{i-1}$, and $e\setminus\{v_i\}$ is a subset of one of the edges consisting only of vertices from $v_1,\ldots,v_{i-1}$. The conjecture of Kalai asserts that every $n$-vertex $r$-uniform hypergraph with more than $\frac{k-1}{r}\binom{n}{r-1}$ 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 »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ős-Gallai 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 non-trivial 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.« less
2. Counting Simplices in Hypergraph Streams

   Chakrabarti, Amit ; Haris, Themistoklis ( October 2022 , Leibniz international proceedings in informatics)

   We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a k-uniform hypergraph H with n vertices and m hyperedges, each hyperedge being a k-sized subset of vertices. A k-simplex 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 k-simplices in H. We design a suite of algorithms for this problem. As with triangle-counting 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 1-pass algorithm thatmore »achieves O(ε^{-2} log δ^{-1} log n⋅ (m/T) (Δ_E + Δ_V^{1-1/k})) space, where Δ_E (respectively, Δ_V) denotes the maximum number of k-simplices 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^{1-1/k}) and Ω(mΔ_V^{1/k}/T) for multi-pass algorithms and Ω(mΔ_E/T) for 1-pass 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.« less
3. On the rank of a random binary matrix

   https://doi.org/10.1137/1.9781611975482.58  

   Cooper, Colin ; Frieze, Alan ; Pegden, Wesley ( January 2019 , Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   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 vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let |C2| be the number of vertices of the 2-core 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 »a basis as a set of n – 1 (k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202.« less
4. Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles

   https://doi.org/10.1017/S096354831900021X  

   Gao, Wei ; Han, Jie ; Zhao, Yi ( November 2019 , Combinatorics, Probability and Computing)

   Abstract Given two k -graphs ( k -uniform hypergraphs) F and H , a perfect F -tiling (or F -factor) in H is a set of vertex-disjoint 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 co-prime. 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.
5. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2  

   Chudnovsky, Maria and ( February 2021 , MATRIX book series)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable 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 clique-stable 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 clique-stable set separation property.