Tiling H H in dense graphs

Nannan Chen, Xizhi Liu, Lin Sun, Guanghui Wang · 2025

Read Tiling H H in dense graphs by Nannan Chen, Xizhi Liu, Lin Sun, Guanghui Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11450.txt.

Introduction

Chen, Liu, Sun, and Wang settle an extremal tiling problem for a letter-shaped tree in this 2025 mathematics paper. Tiling asks how a dense graph can be covered by copies of a fixed small graph. The target here is the H-shaped tree, a specific branching pattern.

The authors determine the two extremal constructions asymptotically, meaning the densest graphs that just avoid perfect tilings. The first construction sits near the complement of two cliques. That shape contrasts with earlier bipartite cases, where one clique's complement ruled. The result disproves a conjecture of Lang that tried to generalize the classic Erdős matching conjecture. The paper redraws the map for this tiling problem.

Catalog record

CREATORNannan Chen, Xizhi Liu, Lin Sun, Guanghui Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11450

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tiling H H in dense graphs Nannan Chen, Xizhi Liu, Lin Sun, Guanghui Wang Abstract We determine asymptotically the two extremal constructions for the tiling problem of the H H -shaped tree. In particular, the first extremal construction is close to the complement of two cliques, in contrast to previously studied bipartite graphs, where the first extremal construction is close to the complement of a single clique. This result refutes one of Lang’s conjectures, which seeks to generalize the Erdős Matching Conjecture. Keywords: tiling problem, average degree, trees, Erdős Matching Conjecture 1 Introduction Fix an integer r\geq 2 , an r -graph \mathcal{G} is a collection of r -subsets of some finite set V . We identify a hypergraph \mathcal{G} with its edge set and use V(\mathcal{G}) to denote its vertex set. The size of V(\mathcal{G}) is denoted by v(\mathcal{G}) . Given a vertex v\in V(\mathcal{G}) , the degree d_{\mathcal{G}}(v) of v in \mathcal{G} is the number of edges in \mathcal{G} containing v . We use \delta(\mathcal{G}) , \Delta(\mathcal{G}) , and d(\mathcal{G}) to denote the minimum degree , the maximum degree , and the average degree of \mathcal{G} , respectively. We will omit the subscript \mathcal{G} if it is clear from the context. Given two r -graphs F and \mathcal{G} , an F -tiling in \mathcal{G} is a collection of vertex-disjoint copies of F in \mathcal{G} . The size of an F -tiling is the number of copies of F in it. The F -matching number \nu(F,\mathcal{G}) of \mathcal{G} is defined as the maximum size of an F -tiling in \mathcal{G} . This concept generalizes the well-studied matching number \nu(\mathcal{G}) of \mathcal{G} , since \nu(\mathcal{G})=\nu(K_{r}^{r},\mathcal{G}) . Here, K_{\ell}^{r} denotes the complete r -graph with \ell vertices. We say \mathcal{G} is F -free if \nu(\mathcal{G})=0 . Numerous works have been dedicated to studying the minimum degree threshold that guarantees an n -vertex r -graph \mathcal{G} contains an F -tiling of a given size, starting from the foundational Corrádi–Hajnal Theorem [ CH63 ] and Hajnal–Szemerédi Theorem [ HS70 ] (see surveys [ KS96 , KSSS02 , KO09a ] ). These questions are now quite well understood for graphs (see e.g. [ KO09b ] ) thanks to decades of effort of numerous researchers. In contrast, the natural problem of determining the average degree threshold that guarantees an n -vertex r -graph \mathcal{G} contains an F -tiling of a given size remains largely unexplored. For convenience, given an r -graph F , an integer n\in\mathbb{N} , and a real number k\in\left[0,n/v(F)\right] , let \mathrm{ex}(n,(k+1)F) denote the maximum number of edges in an n -vertex r -graph \mathcal{G} with \nu(F,\mathcal{G})<k+1 . The case k=0 is known as the Turán problem of F , which is a central topic in Extremal Combinatorics (see surveys [ Kee11 , FS13 ] ), originating from the foundational work Turán [ Tur41 ] (and even earlier, by Mantel [ Man07 ] ). Determining (even asymptotically) the behavior of \mathrm{ex}(n,(k+1)F) as k ranges from 0 to n/v(F) is a very challenging problem in general, with only a few results known in this direction. The simplest case, F=K_{2} , was completely solved by the celebrated Erdős–Gallai Theorem [ EG59 ] . However, the extension of the Erdős–Gallai Theorem becomes quite nontrivial even for very simple structured graphs, such as paths (see e.g. [ Gor11 , BK11 , YZ17 , CL18 , YZ21 ] ) and stars (see e.g. [ LLP13 ] ). For general trees, the asymptotic behavior of \mathrm{ex}(n,(k+1)F) remains largely unknown. For complete graphs, Erdős [ Erd62 ] determined \mathrm{ex}\left(n,(k+1)K_{3}\right) for k\leq\frac{\sqrt{n}}{20} . Moon [ Moo68 ] improved and extended the theorem of Erdős to general r\geq 4 and determined \mathrm{ex}\left(n,(k+1)K_{r}\right) for k\leq\frac{2n}{r^{3}-r^{2}+1}+o(n) (for r=3 , his bound is k\leq\frac{2n}{9}+o(n) ). Akiyama–Frankl [ AF85 ] determined \mathrm{ex}\left(n,(k+1)K_{r}\right) for the case when k=\lfloor n/r\rfloor-1 (see also [ BE78 ] ). A complete determination of \mathrm{ex}\left(n,(k+1)K_{3}\right) was achieved only a decade ago by Allen–Böttcher–Hladký–Piguet [ ABHP15 ] for large n . An asymptotic complete determination of \mathrm{ex}\left(n,(k+1)K_{4}\right) was obtained very recently by Hou et al. [ HHLZ25 ] . Extending the work of Erdős and Moon to general r -graphs F , tight bounds for \mathrm{ex}\left(n,(k+1)F\right) were recently established by Hou et al. in a series of works [ HLL+23 , HHL+23b , HHL+23a , HHL+24 ] for the case where k is much smaller than \frac{\mathrm{ex}(n,F)}{n^{r-1}} . We focus on the case where F is an r -partite r -graph. Given integers s_{1},\ldots,s_{r}\geq 1 , let K_{s_{1},\ldots,s_{r}}^{r} denote the complete r -partite r -graph with parts of sizes s_{1},\ldots,s_{r} . A natural lower bound for \mathrm{ex}(n,\beta n\cdot K_{s_{1},\ldots,s_{r}}^{r}) is provided by the following construction. Construction G_{n,i,\beta}(s_{1},\ldots,s_{r}) : Given integers n\geq r\geq i\geq 1 , 1\leq s_{1}\leq\cdots\leq s_{r} , and a real number \beta\in\left(0,\frac{1}{m}\right) , where m\coloneqq s_{1}+\cdots+s_{r} , let G_{n,i,\beta}(s_{1},\ldots,s_{r}) denote the n -vertex r -graph whose vertex set V has a partition V=V_{1}\cup V_{2} with |V_{1}|=\lfloor\beta(s_{1}+\cdots+s_{i})n\rfloor-1 , such that the edge set of G_{n,i,\beta}(s_{1},\ldots,s_{r}) satisfies \displaystyle G_{n,i,\beta}(s_{1},\ldots,s_{r})=\left\{E\in\binom{V}{r}\colon|E\cap V_{1}|\geq i\right\}. It is easy to observe that \nu(K_{s_{1},\ldots,s_{r}}^{r},G_{n,i,\beta}(s_{1},\ldots,s_{r}))<\beta n for every i\in[r] , and thus \displaystyle\mathrm{ex}(n,\beta n\cdot K_{s_{1},\ldots,s_{r}}^{r})\geq\max\left\{|G_{n,i,\beta}(s_{1},\ldots,s_{r})|\colon i\in[r]\right\}. (1) For the case (s_{1},\ldots,s_{r})=(1,\ldots,1) , straightforward calculations show that the maximum value of |G_{n,i,\beta}(1,\ldots,1)| is achieved when either i=1 or i=r . The Erdős–Gallai Theorem [ EG59 ] mentioned above states that the inequality in ( 1 ) holds with equality when r=2 and (s_{1},s_{2})=(1,1) . Extending the Erdős–Gallai Theorem to r\geq 3 is a major open problem in Extremal Combinatorics. The famous Matching Conjecture by Erdős [ Erd65 ] states that, for (s_{1},\ldots,s_{r})=(1,\ldots,1) and \beta\in[0,1/r] , the inequality in ( 1 ) also holds with equality, i.e., for n\geq r(k+1)-1 , \displaystyle\mathrm{ex}(n,(k+1)\cdot K_{1,\ldots,1}^{r})=\max\left\{\binom{n}{r}-\binom{n-k}{r},~\binom{r(k+1)-1}{r}\right\}. The Erdős Matching Conjecture for the case r=3 was solved by Łuczak–Mieczkowska [ ŁM14 ] for large n , and by Frankl [ Fra17a ] for all n . However, the case r\geq 4 remains open in general (see e.g. [ HLS12 , Fra13 , ŁM14 , Fra17a , Fra17b ] for some recent progress on this topic). Going one step beyond the Erdős Matching Conjecture, Lang [ Lan23 ] proposed the following conjecture for general r -partite r -graphs. Conjecture 1.1 (Lang [ Lan23 , Conjecture 10.1] ) . Let r\geq 2 and 1\leq s_{1}\leq\cdots\leq s_{r} be integers. Let m\coloneqq s_{1}+\cdots+s_{r} . Suppose that F is a spanning subgraph of K_{s_{1},\ldots,s_{r}}^{r} . Then for every real number \beta\in\left(0,\frac{1}{m}\right) , \displaystyle\mathrm{ex}(n,\beta n\cdot F)=\max\left\{|G_{n,i,\beta}(s_{1},\ldots,s_{r})|\colon i\in[r]\right\}+o(n^{r}). The conjecture for the case where F is a complete bipartite graphs follows from the following theorem by Grosu–Hladký [ GH12 ] . Theorem 1.2 (Grosu–Hladký [ GH12 ] ) . Let t\geq s\geq 1 be integers. Suppose that F is a spanning subgraph of K_{s,t} . Then, for every real number \beta\in\left(0,\frac{1}{s+t}\right) , \displaystyle\mathrm{ex}(n,\beta n\cdot F)\leq\left(\max\left\{\frac{s\beta\left(2-s\beta\right)}{2},~\frac{(s+t)^{2}\beta^{2}}{2}\right\}+o(1)\right)n^{2}. Results by Hou et al. [ HHL+23b , HHL+23a , HHL+24 ] show that Conjecture 1.1 holds for certain class (see Section 6 ) of r -partite r -graphs F when k lies in intervals \displaystyle\left[0,~\frac{\varepsilon\cdot\mathrm{ex}(n,F)}{n^{r-1}}\right],\quad\left[\frac{\varepsilon\cdot\mathrm{ex}(n,F)}{n^{r-1}},~\varepsilon n\right],\quad\text{and}\quad\left[\frac{n}{v(F)}-\varepsilon n,~\frac{n}{v(F)}\right], where \varepsilon>0 is a constant depending only on F . A conjecture similar to Conjecture 1.1 was proposed earlier by Gan et al. [ GHSW23 ] for the r -partite r -graph Y_{r,b} , where Y_{r,b} is the r

Read the complete text