Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Turán's theorem
Summary
In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph.
An example of an -vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the Turán graph . Turán's theorem states that the Turán graph has the largest number of edges among all Kr+1-free n-vertex graphs.
Turán's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941. The special case of the theorem for triangle-free graphs is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician.
Turán's theorem states that every graph with vertices that does not contain as a subgraph has at most as many edges as the Turán graph . For a fixed value of , this graph hasedges, using little-o notation. Intuitively, this means that as gets larger, the fraction of edges included in gets closer and closer to . Many of the following proofs only give the upper bound of .
list five different proofs of Turán's theorem.
Many of the proofs involve reducing to the case where the graph is a complete multipartite graph, and showing that the number of edges is maximized when there are parts of size as close as possible to equal.
This was Turán's original proof. Take a -free graph on vertices with the maximal number of edges. Find a (which exists by maximality), and partition the vertices into the set of the vertices in the and the set of the other vertices.
Now, one can bound edges above as follows:
There are exactly edges within .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related lectures (7)
Statistical analysis of network data
Covers stochastic properties, network structures, models, statistics, centrality measures, and sampling methods in network data analysis.
Extreme Value Time Series: Modelling and Dependence
Explores extremal limit theorems, point processes, and multivariate extremes in extreme value time series modelling, emphasizing the effect of local dependence on extreme values.
Extreme Value Theory: Applications and Estimation
Explores Extreme Value Theory applications, estimation strategies, and modelling techniques for statistical analysis of extremes in time series.
Related publications (13)
Related people (2)
Related concepts (8)
Clique (graph theory)
In the mathematical area of graph theory, a clique (ˈkliːk or ˈklɪk) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
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.
Claw-free graph
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph.