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 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ő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. 

   more » « less
2. Vertex degree sums for perfect matchings in 3-uniform hypergraphs

   Zhang, Yi and ( September 2018 , The Electronic journal of combinatorics)

   We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without isolated vertex. Suppose that $H$ is a 3-uniform hypergraph whose order $n$ is sufficiently large and divisible by $3$. If $H$ contains no isolated vertex and $\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different \emph{space barrier} from the one for the corresponding Dirac problem. 

   more » « less
3. Berge Cycles in Non-Uniform Hypergraphs

   https://doi.org/10.37236/9346  

   Füredi, Zoltán ; Kostochka, Alexandr ; Luo, Ruth ( July 2020 , The Electronic Journal of Combinatorics)

   We consider two extremal problems for set systems without long Berge cycles. First we give Dirac-type minimum degree conditions that force long Berge cycles. Next we give an upper bound for the number of hyperedges in a hypergraph with bounded circumference. Both results are best possible in infinitely many cases. 

   more » « less
4. On the connectivity of proper colorings of random graphs and hypergraphs

   https://doi.org/10.1002/rsa.20912  

   Anastos, Michael ; Frieze, Alan ( February 2020 , Random Structures & Algorithms)

   Let Ω_q=Ω_q(H) denote the set of proper [q]‐colorings of the hypergraphH. Let Γ_qbe the graph with vertex set Ω_qwhere two coloringsσ,τare adjacent iff the corresponding colorings differ in exactly one vertex. We show that ifH=H_n,m;k, k ≥ 2, the randomk‐uniform hypergraph withV=[n] andm=dn/khyperedges then w.h.p. Γ_qis connected ifdis sufficiently large and. This is optimal up to the first order ind. Furthermore, with a few more colors, we find that the diameter of Γ_qisO(n) w.h.p., where the hidden constant depends ond. So, with this choice ofd,q, the natural Glauber dynamics Markov Chain on Ω_qis ergodic w.h.p.

    

   more » « less
5. On the complexity of binary polynomial optimization over acyclic hypergraphs

   https://doi.org/10.1137/1.9781611977073.105  

   Alberto Del Pia and Silvia Di Gregorio ( January 2022 , Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)

   In this work we advance the understanding of the fundamental limits of computation for Binary Polynomial Optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whose corresponding hypergraph is β-acyclic. We note that the β-acyclicity assumption is natural in several applications including relational database schemes and the lifted multicut problem on trees. Due to the novelty of our proving technique, we obtain an algorithm which is interesting also from a practical viewpoint. This is because our algorithm is very simple to implement and the running time is a polynomial of very low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs, since the problem is NP-hard on α-acyclic instances. Our algorithm can also be applied to any general BPO problem that contains β-cycles. For these problems, the algorithm returns a smaller instance together with a rule to extend any optimal solution of the smaller instance to an optimal solution of the original instance. 

   more » « less