An official website of the United States government
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.
more »
« less
Hypergraphs Accumulate
Abstract We showthat for every integer $$k\geqslant 3$$ the set of Turán densities of $$k$$-uniform hypergraphs has an accumulation point in $[0,1)$. In particular, $1/2$ is an accumulation point for the set of Turán densities of $$3$$-uniform hypergraphs.
more »
« less
- PAR ID:
- 10566875
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- Volume:
- 2025
- Issue:
- 2
- ISSN:
- 1073-7928
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended tok‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.more » « less
-
We show that there is an absolute constant c > 0 c>0 such that the following holds. For every n > 1 n > 1 , there is a 5-uniform hypergraph on at least 2 2 c n 1 / 4 2^{2^{cn^{1/4}}} vertices with independence number at most n n , where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for k k -uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.more » « less
-
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
-
Motivated by the Erdős–Szekeres convex polytope conjecture in $$\mathbb{R}^{d}$$ , we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers $$n>k\geqslant 5$$ , what is the minimum integer $$g_{k}(n)$$ such that any $$k$$ -uniform hypergraph on $$g_{k}(n)$$ vertices with the property that any set of $k+1$ vertices induces 0, 2, or 4 edges, contains an independent set of size $$n$$ . Our main result shows that $$g_{k}(n)>2^{cn^{k-4}}$$ , where $c=c(k)$ .more » « less
