A completion of the proof of the Edge-statistics Conjecture
Advances in Combinatorics · 2004
DOI: 10.19086/aic.12047 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Combinatorics, 2004. Verfasst von Lisa Sauerman und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number vertices as $H$; this quantity is known as the _inducibility_ of $H$. More generally, one can define the inducibility of a family of graphs in the analogous way. Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join each pair of vertices independently by an edge with probability $\binom{k}{2}^{-1}$. The expected number of $k$-vertex induced subgraphs with exactly one edge is $e^{-1}+o(1)$. So, the inducibility of large graphs with a single edge is at least $e^{-1}+o(1)$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $k$-vertex graphs with exactly $l$ edges where $0
Zitieren
APA
Sauerman, L., & Fox, J. (2004). A completion of the proof of the Edge-statistics Conjecture. Advances in Combinatorics. https://doi.org/10.19086/aic.12047
Vancouver
Sauerman L, Fox J. A completion of the proof of the Edge-statistics Conjecture. Advances in Combinatorics. 2004. doi:10.19086/aic.12047
BibTeX
@article{Sauerman2004,
author = {Sauerman, Lisa and Fox, Jacob},
title = {A completion of the proof of the Edge-statistics Conjecture},
journal = {Advances in Combinatorics},
year = {2004},
doi = {10.19086/aic.12047}
}
EUVIMED