Turán graph Created 2026-09-29 Updated 2026-10-14
The Turán graph is a complete multipartite graph with independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when .[ref]
Graph Theory by Reinhard Diestel. third electronic edition (2005), §7.1, printed p. 165, definition of Turán graphs and convention for empty partition sets
In this example, the independent sets are , and . Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form . Conversely, every choice of one vertex from each part is a triangle in a graph, giving triangles in a graph. Clique exclusion here does not mean triangle-free.
For the exact count, Euclidean division writes , where uses the floor function and is the remainder, with . There are parts of size and of size . For any part sizes summing to , count cross edges by expanding the square:ThereforeFor , we have , giving . The Quadratic Turan edge bound gives instead: the exact correction subtracts .
Balancing is an integer optimization with a simple reason. If two part sizes satisfy , moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by . For eight vertices, parts give edges; moving one vertex produces and edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.
Unit-ideal identity for powers Created 2026-10-06 Updated 2026-11-05
If , expand its power . By the pigeonhole principle, each monomial contains some . Collecting terms expresses as a linear combination of these powers. This lets one use a common denominator exponent in localization arguments.
Universal lossless shortening is impossible Created 2026-10-13 Updated 2026-11-05
Fix . There is no injective function from all length- binary strings to binary strings of length strictly less than . There are possible inputs, but even allowing the empty string gives onlypossible shorter outputs. The finite geometric series and pigeonhole principle leave at least two inputs sharing an output, which prevents exact decoding. For , eight inputs compete for the empty string and the six strings
0, 1, 00, 01, 10, 11.This counting argument includes any file header or other information sent to the decoder. An algorithm chosen separately for each input must also be identified to the receiver; its description is not free. A useful compressor saves space on some inputs while leaving others unchanged or making them longer. Lossy compression avoids the exact-recovery requirement by deliberately allowing several inputs to share an output.
