TL;DR
This paper provides an asymptotic solution to the tiling problem for a specific $H$-shaped tree, determining the maximum number of edges a graph can have without containing a certain number of vertex-disjoint copies of $H$. Crucially, the authors show that the extremal construction for this tree is structurally different from previously studied bipartite graphs, thereby refuting a recent conjecture by Lang that attempted to generalize the Erdős Matching Conjecture.
What Problem Does This Paper Address?
In extremal graph theory, a "tiling" (or perfect matching) problem asks: how "dense" must a large graph $G$ be to guarantee it contains $k$ vertex-disjoint copies of a smaller graph $H$? While much is known about the minimum degree required for such tilings, the average degree (or total edge count) threshold remains largely unexplored for many structures.
The authors focus on the Turán-type problem: finding $ex(n, (k+1)F)$, the maximum number of edges in an $n$-vertex graph that does not contain $k+1$ disjoint copies of $F$. Specifically, they investigate the case where $F$ is an $H$-shaped tree (a graph with 6 vertices and 5 edges). This is a direct step toward understanding the "density tiling problem" for general trees and testing the limits of existing conjectures in the field.
Methods
The proof relies on the "Regularity Method," a cornerstone of modern extremal combinatorics. The key steps include:
- Szemerédi’s Regularity Lemma: Partitioning the large graph into a constant number of clusters where the edges between clusters behave almost randomly.
- Reduced Graphs: Creating a smaller "reduced graph" $R$ where each vertex represents a cluster and edges represent dense, regular pairs.
- The Blowup Lemma: A powerful tool that allows the authors to "blow up" a tiling found in the small reduced graph $R$ into a much larger tiling in the original graph $G$.
- Local Estimation: The heart of the paper involves a grueling, exhaustive case-by-case analysis (Section 5) of how copies of $H$ can be embedded into small configurations. This "local" math is what ultimately determines the global edge threshold.
Datasets
Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and logical derivations rather than empirical datasets.
Key Insights and Ideas
- Refuting Lang’s Conjecture: Lang (2023) conjectured that for any $r$-partite graph $F$, the extremal construction would always be one of a few standard types (essentially the complement of a single clique). This paper shows that for the $H$-shaped tree, the extremal construction is actually close to the complement of two cliques.
- Rigidity vs. Non-rigidity: The authors introduce (or refine) the concept of "rigid" graphs. A graph is rigid if its covering numbers follow a specific pattern. They propose that Lang's conjecture might still hold for rigid graphs, but the $H$-shaped tree is a prime example of a non-rigid graph where the conjecture fails.
- Structural Complexity: The discovery that the extremal behavior of a simple tree can be more complex than that of complete bipartite graphs suggests that the "average degree" tiling problem is much deeper than the "minimum degree" version.
Key Results
The main result is Theorem 1.3, which provides the asymptotic value for the maximum number of edges: $$ex(n, \beta n \cdot H) = (\Xi(\beta) + o(1)) n^2$$ Where the threshold function $\Xi(\beta)$ is defined as:
- $3\beta(1 - 3\beta)$ if $\beta \in [0, 1/9]$
- $18\beta^2$ if $\beta \in [1/9, 1/6]$
This formula shows a "phase transition" at $\beta = 1/9$, where the optimal way to avoid the tiling changes its structural form.
Limitations and Future Work
- Non-rigid Graphs: The authors acknowledge that the behavior of non-rigid graphs remains mysterious. They propose a new, weaker conjecture (Problem 6.3) for these cases.
- General Trees: While they solved the problem for the $H$-shaped tree, the general problem for an arbitrary tree $T$ remains open (Problem 6.4).
- Hypergraphs: The paper touches on $r$-graphs (hypergraphs), but the main result is focused on standard graphs ($r=2$). Extending these results to 3-uniform hypergraphs or higher is a significant challenge due to the increased complexity of hypergraph regularity.
Summary updated