|
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 (mathematician), Arthur Stone, who proved it in 1946, and it has been described as the “fundamental theorem of extremal graph theory”. 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''; ''K''''r'') = ''t''''r'' − 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'' = ''K''''r''('' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Extremal Graph Theory
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various Graph property, graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory. Extremal graph theory is closely related to fields such as Ramsey theory, spectral graph theory, computational complexity theory, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
