Kurz gefasst
Fachartikel in der Zeitschrift Discrete Analysis, 2025.
Abstract (Originalsprache)
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three sparse versions of the blow-up lemma: one for embedding spanning graphs with maximum degree $\Delta$ in subgraphs of $G(n,p)$ with $p=C(\log n/n)^{1/\Delta}$; one for embedding spanning graphs with maximum degree $\Delta$ and degeneracy $D$ in subgraphs of $G(n,p)$ with $p=C_\Delta\big(\log n/n\big)^{1/(2D+1)}$; and one for embedding spanning graphs with maximum degree $\Delta$ in $(p,cp^{\max(4,(3\Delta+1)/2)}n)$-bijumbled graphs. We also consider various applications of these lemmas.
Zitieren
APA
(2025). blow-up-lemmas-for-sparse-graphs. Discrete Analysis. https://doi.org/10.19086/da.143410
Vancouver
blow-up-lemmas-for-sparse-graphs. Discrete Analysis. 2025. doi:10.19086/da.143410
BibTeX
@article{euvimed2025,
title = {blow-up-lemmas-for-sparse-graphs},
journal = {Discrete Analysis},
year = {2025},
doi = {10.19086/da.143410}
}
EUVIMED