More Like this

1. 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
2. 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
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. Off‐Diagonal Ramsey Numbers for Slowly Growing Hypergraphs

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

   Mattheus, Sam; Mubayi, Dhruv; Nie, Jiaxi; Verstraëte, Jacques (January 2025, Random Structures & Algorithms)

   ABSTRACT For ak‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph isslowly growingif there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for ,In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers. 

   more » « less
5. Representing Hypergraphs by Point-Line Incidences

   Dobler, Alexander; Kobourov, Stephen; Lenhart, William; Mchedlidze, Tamara; Noellenburg, Martin; Symvonis, Antonios (March 2024, EuroCG)

   We consider hypergraph visualization that represent vertices as points and hyperedges as lines with few bends passing through points of their incident vertices. Guided by point-line incidence theory we show several theoretical results: if every vertex is part of at most two hyperedges, then we can find such a visualization without bends. There exist hypergraphs with three vertices per hyperedge and three hyperedges incident to each vertex requiring an arbitrary number of bends. It is ETR-hard to decide whether an arbitrary hypergraph can be visualized without bends. This only answers some interesting questions for such visualizations and we conclude with many open research questions. 

   more » « less