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. On 2- and 3-Factorizations of Complete 3-Uniform Hypergraphs of Order up to 9

   Adams, P; El-Zanati, S; Florido, P; Turner, W. (January 2020, The Australasian journal of combinatorics)

   A $$k$$-factorization of the complete $$t$$-uniform hypergraph $$K^{(t)}_{v}$$ is an $$H$$-decomposition of $$K^{(t)}_{v}$$ where $$H$$ is a $$k$$-regular spanning subhypergraph of $$K^{(t)}_{v}$$. We use nauty to generate the 2-regular and 3-regular spanning subhypergraphs of $$K^{(3)}_v$$ for $$v\leq 9$$ and investigate which of these subhypergraphs factorize $$K^{(3)}_v$$ or $$K^{(3)}_v-I$$, where $$I$$ is a 1-factor. We settle this question for all but two of these subhypergraphs. 

   more » « less
3. Vertex Degree Sums for Matchings in 3-Uniform Hypergraphs

   https://doi.org/10.37236/8627  

   Zhang, Yi; Zhao, Yi; Lu, Mei (October 2019, The Electronic Journal of Combinatorics)

   Let $n, s$ be positive integers such that $$n$$ is sufficiently large and $$s\le n/3$$. Suppose $$H$$ is a 3-uniform hypergraph of order $$n$$ without isolated vertices. If $$\deg(u)+\deg(v) > 2(s-1)(n-1)$$ for any two vertices $$u$$ and $$v$$ that are contained in some edge of $$H$$, then $$H$$ contains a matching of size $$s$$. This degree sum condition is best possible and confirms a conjecture of the authors [Electron. J. Combin. 25 (3), 2018], who proved the case when $s= n/3$. 

   more » « less
4. Extremal Numbers and Sidorenko’s Conjecture

   https://doi.org/10.1093/imrn/rnae071  

   Conlon, David; Lee, Joonkyung; Sidorenko, Alexander (April 2024, International Mathematics Research Notices)

   Abstract Sidorenko’s conjecture states that, for all bipartite graphs $$H$$, quasirandom graphs contain asymptotically the minimum number of copies of $$H$$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko’s conjecture does not hold for a particular $$r$$-partite $$r$$-uniform hypergraph $$H$$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $$\textrm{ex}(n,H)$$, the maximum number of edges in an $$n$$-vertex $$H$$-free $$r$$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $$3$$-partite $$3$$-uniform tight cycles. 

   more » « less
5. Large monochromatic components in hypergraphs with large minimum codegree

   https://doi.org/10.1002/jgt.23044  

   Bal, Deepak; DeBiasio, Louis (October 2023, Journal of Graph Theory)

   Abstract A result of Gyárfás says that for every 3‐coloring of the edges of the complete graph , there is a monochromatic component of order at least , and this is best possible when 4 divides . Furthermore, for all and every ‐coloring of the edges of the complete ‐uniform hypergraph , there is a monochromatic component of order at least and this is best possible for all . Recently, Guggiari and Scott and independently Rahimi proved a strengthening of the graph case in the result above which says that the same conclusion holds if is replaced by any graph on vertices with minimum degree at least ; furthermore, this bound on the minimum degree is best possible. We prove a strengthening of the case in the result above which says that the same conclusion holds if is replaced by any ‐uniform hypergraph on vertices with minimum ‐degree at least ; furthermore, this bound on the ‐degree is best possible. 

   more » « less