Turan's theorem: most edges with no clique on r+1 vertices

The maximum is attained by the complete \(r\)-partite graph with parts as equal as possible, and that graph is the unique extremal example.

Usage

morie_turan_number(n, r)

Arguments

n

Vertices.

r

Forbid \(K_{r+1}\).

Value

A list with count, rounded_formula, part_sizes, attained, formula_is_exact.

Details

The familiar \((1 - 1/r)n^2/2\) is exact ONLY when \(r\) divides \(n\); otherwise it is an upper bound. At \(n = 10, r = 3\) it gives 33.33 against an exact 33. Both are returned so the looseness is visible.

References

Turan P (1941). Bollobas B (2004), Ch VI.

Examples

morie_turan_number(n = 5L, r = 5L)
#> $count
#> [1] 10
#> 
#> $rounded_formula
#> [1] 10
#> 
#> $formula_is_exact
#> [1] TRUE
#> 
#> $part_sizes
#> [1] 1 1 1 1 1
#> 
#> $construction_edges
#> [1] 10
#> 
#> $attained
#> [1] TRUE
#> 
#> $forbidden_clique
#> [1] 6
#> 
#> $n
#> [1] 5
#> 
#> $r
#> [1] 5
#> 
#> $method
#> [1] "Turan's theorem (Turan 1941)"
#>