EUVIMEDEUVIMED entdecken
Crossref

A completion of the proof of the Edge-statistics Conjecture

Lisa Sauerman, Jacob Fox

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →