Erdős–Stone theorem

Erdős–Stone theorem In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an H-free graph for a non-complete graph H. It is named after Paul Erdős and Arthur Stone, chi l'ha dimostrato 1946,[1] and it has been described as the “fundamental theorem of extremal graph theory”.[2] Contenuti 1 Statement for Turán graphs 2 Statement for arbitrary non-bipartite graphs 3 Turán density 4 Prova 5 Quantitative results 6 Notes Statement for Turán graphs The extremal number ex(n; H) is defined to be the maximum number of edges in a graph with n vertices not containing a subgraph isomorphic to H; see the Forbidden subgraph problem for more examples of problems involving the extremal number. Turán's theorem says that ex(n; Kr) = tr − 1(n), the number of edges of the Turán graph T(n, r − 1), and that the Turán graph is the unique such extremal graph. The Erdős–Stone theorem extends this result to H=Kr(t), the complete r-partite graph with t vertices in each class, which is the graph obtained by taking Kr and replacing each vertex with t independent vertices: {stile di visualizzazione {mbox{ex}}(n;K_{r}(t))= sinistra({frac {r-2}{r-1}}+o(1)Giusto){n scegli 2}.} Statement for arbitrary non-bipartite graphs If H is an arbitrary graph whose chromatic number is r > 2, then H is contained in Kr(t) whenever t is at least as large as the largest color class in an r-coloring of H, but it is not contained in the Turán graph T(n,r − 1), as this graph and therefore each of its subgraphs can be colored with r − 1 colors. It follows that the extremal number for H is at least as large as the number of edges in T(n,r − 1), and at most equal to the extremal function for Kr(t); questo è, {stile di visualizzazione {mbox{ex}}(n;H)= sinistra({frac {r-2}{r-1}}+o(1)Giusto){n scegli 2}.} For bipartite graphs H, però, the theorem does not give a tight bound on the extremal function. It is known that, when H is bipartite, ex(n; H) = o(n2), and for general bipartite graphs little more is known. See Zarankiewicz problem for more on the extremal functions of bipartite graphs.

Turán density Another way of describing the Erdős–Stone theorem is using the Turán density of a graph {stile di visualizzazione H} , which is defined by {stile di visualizzazione pi (H)=lim _{infty }{frac {{testo{ex}}(n;H)}{n scegli 2}}} . This determines the extremal number {stile di visualizzazione {testo{ex(n; H)}}} up to an additive {stile di visualizzazione o(n^{2})} error term. It can also be thought of as follows: given a sequence of graphs {stile di visualizzazione G_{1},G_{2},punti } , each not containing {stile di visualizzazione H} , such that the number of vertices goes to infinity, the Turán density is the maximum possible limit of their edge densities. The Erdős–Stone theorem determines the Turán density for all graphs, showing that any graph {stile di visualizzazione H} with chromatic number {displaystyle r>1} has a Turán density of {stile di visualizzazione pi (H)={frac {r-2}{r-1}}.} Proof One proof of the Erdős–Stone theorem uses an extension of the Kővári–Sós–Turán theorem to hypergraphs, as well as the supersaturation theorem, by creating a corresponding hypergraph for every graph that is {stile di visualizzazione K_{r}(t)} -free and showing that the hypergraph has some bounded number of edges. The Kővári–Sós–Turán says, tra l'altro, that the extremal number of {stile di visualizzazione K_{2}(t)} , the complete bipartite graph with {stile di visualizzazione t} vertices in each part, è al massimo {stile di visualizzazione {testo{ex}}(K_{2}(t);n)leq Cn^{2-1/t}} for a constant {stile di visualizzazione C} . This can be extended to hypergraphs: definendo {stile di visualizzazione K_{S,punti ,S}^{(r)}} to be the {stile di visualizzazione r} -partite {stile di visualizzazione r} -graph with {stile di visualizzazione s} vertices in each part, poi {stile di visualizzazione {testo{ex}}(K_{S,punti ,S}^{(r)},n)leq Cn^{r-s^{1-r}}} per qualche costante {stile di visualizzazione C} .[citazione necessaria] Adesso, for a given graph {displaystyle H=K_{r}(t)} insieme a {displaystyle r>1,sgeq 1} , and some graph {stile di visualizzazione G} insieme a {stile di visualizzazione n} vertices that does not contain a subgraph isomorphic to {stile di visualizzazione H} , we define the {stile di visualizzazione r} -graph {stile di visualizzazione F} with the same vertices as {stile di visualizzazione G} and a hyperedge between vertices in {stile di visualizzazione F} if they form a clique in {stile di visualizzazione G} . Nota che se {stile di visualizzazione F} contains a copy of {stile di visualizzazione K_{S,punti ,S}^{(r)}} , then the original graph {stile di visualizzazione G} contains a copy of {stile di visualizzazione H} , as every pair of vertices in distinct parts must have an edge, but no two vertices in the same part contain an edge. così. {stile di visualizzazione F} contains no copies of {stile di visualizzazione K_{S,punti ,S}^{r}} , and so it has {stile di visualizzazione o(n^{r})} hyperedges, indicating that there are {stile di visualizzazione o(n^{r})} copie di {stile di visualizzazione K_{r}} in {stile di visualizzazione G} . By supersaturation, this means that the edge density of {stile di visualizzazione G} is within {stile di visualizzazione o(1)} of the Turán density of {stile di visualizzazione K_{r}} , che è {stile di visualizzazione {frac {r-2}{r-1}}} by Turán's theorem; così, the edge density is bounded above by {stile di visualizzazione {frac {r-2}{r-1}}+o(1)} .

D'altro canto, we can achieve this bound by taking the Turán graph {stile di visualizzazione T(n,r-1)} , which contains no copies of {stile di visualizzazione K_{r}(t)} but has {stile di visualizzazione a sinistra({frac {r-2}{r-1}}-o(1)Giusto){n scegli 2}} bordi, showing that this value is the maximum and concluding the proof.

Quantitative results Several versions of the theorem have been proved that more precisely characterise the relation of n, r, t and the o(1) term. Define the notation[3] sr,e(n) (per 0 < ε < 1/(2(r − 1))) to be the greatest t such that every graph of order n and size {displaystyle left({frac {r-2}{2(r-1)}}+varepsilon right)n^{2}} contains a Kr(t). Erdős and Stone proved that {displaystyle s_{r,varepsilon }(n)geq left(underbrace {log cdots log } _{r-1}nright)^{1/2}} for n sufficiently large. The correct order of sr,ε(n) in terms of n was found by Bollobás and Erdős:[4] for any given r and ε there are constants c1(r, ε) and c2(r, ε) such that c1(r, ε) log n < sr,ε(n) < c2(r, ε) log n. Chvátal and Szemerédi[5] then determined the nature of the dependence on r and ε, up to a constant: {displaystyle {frac {1}{500log(1/varepsilon )}}log ng n} for sufficiently large n. Notes ^ Erdős, P.; Calcolo, UN. H. (1946). "On the structure of linear graphs". Bollettino dell'American Mathematical Society. 52 (12): 1087–1091. doi:10.1090/S0002-9904-1946-08715-7. ^ Bollobás, Bela (1998). Modern Graph Theory. New York: Springer-Verlag. pp. 120. ISBN 0-387-98491-7. ^ Bollobás, Bela (1995). "Extremal graph theory". In R. l. Graham; M. Grötschel; l. Sposo (eds.). Handbook of combinatorics. Altro. p. 1244. ISBN 0-444-88002-X. ^ Bollobás, B.; foresta, P. (1973). "On the structure of edge graphs". Bollettino della London Mathematical Society. 5 (3): 317–321. doi:10.1112/blms/5.3.317. ^ Scattò, V.; Lei appartiene a te, e. (1981). "On the Erdős-Stone theorem". Giornale della London Mathematical Society. 23 (2): 207–214. doi:10.1112/jlms/s2-23.2.207. Categorie: Extremal graph theoryTheorems in graph theoryPaul Erdős

Se vuoi conoscere altri articoli simili a Erdős–Stone theorem puoi visitare la categoria Extremal graph theory.

lascia un commento

L'indirizzo email non verrà pubblicato.

Vai su

Utilizziamo cookie propri e di terze parti per migliorare l'esperienza dell'utente Maggiori informazioni