Turán Graph¶
The balanced complete r-partite graph T(n,r), formed by making nearly equal vertex blocks independent and joining every cross-block pair, uniquely maximizing edges among n-vertex graphs with no K_(r+1).
Core Idea¶
For integers \(1\le r\le n\), the Turán graph (T(n,r)) is the complete ®-partite simple graph whose part sizes differ by at most one. Write
Then (T(n,r)) has (s) independent parts of size (q+1) and (r-s) independent parts of size (q). Two vertices are adjacent exactly when they lie in different parts. Thus the construction combines three commitments that must remain together: partition the vertex set into exactly ® nonempty blocks, balance the blocks as evenly as integer arithmetic permits, and complete every cross-block adjacency while leaving every within-block pair nonadjacent.
Scope of Application¶
The home domain is extremal graph theory, especially forbidden-subgraph problems. The basic problem asks for the largest number of edges in an (n)-vertex graph avoiding a fixed graph (H). The corresponding maximum is (operatorname{ex}(n,H)). For cliques, Turán's 1941 result gives the exact answer and unique equality structure: (operatorname{ex}(n,K_{r+1})=e(T(n,r))).
The construction also sits naturally in multipartite graph theory. Its parts are independent color classes, its chromatic number is ® for \(1\le r\le n\), and its complement is the disjoint union of ® cliques whose orders are as equal as possible.
Clarity¶
The concept separates three levels often blurred in informal usage: construction, objective value, and theorem. (T(n,r)) is the constructed graph. (t_r(n)=e(T(n,r))) is its edge count and the relevant Turán number. Turán's theorem proves that this value is optimal and characterizes equality. Keeping the three distinct prevents statements such as “the Turán graph is the bound” or “a graph with nearly the bound is the Turán graph.”
Manages Complexity¶
The Turán graph compresses an enormous feasible family—all (K_{r+1})-free graphs on (n) vertices—into a single canonical equality object. Instead of comparing arbitrary edge sets, a reasoner can calculate one balanced multipartite construction, read off the optimum, and use deviations from its structure to understand why a candidate graph loses edges or creates the forbidden clique.
Abstract Reasoning¶
Clique exclusion. Since every edge lies between parts, a clique contains at most one vertex from each of the ® parts. Hence (omega(T(n,r))=r) and (K_{r+1}) is absent. Conversely, selecting one vertex from each nonempty part produces a (K_r).
Balancing inference. Suppose a complete ®-partite graph has two parts of sizes (a) and (b) with \(a\ge b+2\).
Knowledge Transfer¶
Within graph theory the construction transfers as an exact mechanism. The same (n,r) partition and completion rule can serve as a forbidden-clique extremizer, an equitable-coloring completion, a complement-of-balanced-cliques representation, a benchmark graph for spectral or geometric questions, and a base construction in stability arguments. In every case the graph is literally (T(n,r)), not an analogy.
Relationships to Other Abstractions¶
Current abstraction Turán Graph Domain-specific
Parents (1) — more general patterns this builds on
-
Turán Graph presupposes Partition Prime
Turán Graph strictly presupposes
prime:partition: its vertex set is divided into disjoint, exhaustive partite blocks, and the balance and adjacency rules are defined entirely relative to those blocks.
Hierarchy path (1) — routes to 1 parentless root
- Turán Graph → Partition → Set and Membership
Neighborhood in Abstraction Space¶
Turán Graph sits in a sparse region of the domain-specific corpus (81st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Coloring Games & Drawings (7 abstractions)
Nearest neighbors
- Ruzsa–Szemerédi Problem — 0.83
- Goldberg–Seymour Theorem — 0.83
- Matching — 0.82
- Dense Graph — 0.82
- Erdős–Ko–Rado Theorem — 0.81
Computed from structural-signature embeddings · 2026-09-08