Turán number

The complements of the lines of the Fano plane, which form a Turán (7,5,4)-system. T(7,5,4) = 7. The graph is 4-uniform, order 7, and any 5 vertices selected induce an edge.

In mathematics, the Turán number $T(n,k,r)$ for $r$-uniform hypergraphs of order $n$ is the smallest number of $r$-edges such that every induced subgraph on $k$ vertices contains an edge. This number was determined for $r=2$ by (Turán 1941), and the problem for general $r$ was introduced in (Turán 1961). The paper (Sidorenko 1995) gives a survey of Turán numbers.

Definitions

Fix a set $X$ of $n$ vertices. For given $r$, an $r$-edge or block is a set of $r$ vertices. A set of blocks is called a Turán $(n,k,r)$-system ($n\ge k\ge r$) if every $k$-element subset of $X$ contains a block. The Turán number $T(n,k,r)$ is the minimum size of such a system.

Examples

The complements of the lines of the Fano plane form a Turán $(7,5,4)$-system. $T(7,5,4)=7$.

The following values and bounds for $T(n,6,4)$ are known:

$n$	7	8	9	10	11	12	13	14	15	16
$T(n,6,4)$	3	6	12	20	34	51	74–79	104–115	142–161	190–220

This sequence appears as (sequence A348464 in the OEIS).

The following values and bounds for $T(n,7,4)$ are known:

$n$	8	9	10	11	12	13	14	15	16
$T(n,7,4)$	2	5	10	17	26	38–39	54–56	74–80	99–108

It is also known that $T(17,5,4)\ge 627$ and $T(18,5,4)\ge 807$

Relations to other combinatorial designs

It can be shown that

$T(n,k,r)\ge (\genfrac{}{}{0ex}{}{n}{r}){(\genfrac{}{}{0ex}{}{k}{r})}^{-1}.$

Equality holds if and only if there exists a Steiner system $S(n-k,n-r,n)$.

An $(n,r,k,r)$-lotto design is an $(n,k,r)$-Turán system. Thus, $T(n,k,r)=L(n,r,k,r)$.

Covering designs

Main article: Covering design

The covering number $C(v,k,t)$ is the minimum number of $k$-element subsets of a $v$-set such that every $t$-element subset is contained in at least one of the chosen $k$-subsets. By passing to complementary subsets, covering numbers and Turán numbers are related by the identity

$T(n,\ell ,r)=C(n,n-r,n-\ell ).$

Although the two are thus equivalent, they have historically been studied in different parameter ranges: Turán problems typically have $n$ large relative to $\ell$ and $r$, while covering problems typically have $n$ large relative to $n-r$ and $n-\ell$.

See also

• Forbidden subgraph problem
• Combinatorial design

References

• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8, https://archive.org/details/handbookofcombin0000unse 
• Hazewinkel, Michiel, ed. (2001), "Turán number", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page 
• Gordon, Daniel M.; Kuperberg, Greg; Patashnik, Oren (1995). "New constructions for covering designs". Journal of Combinatorial Designs 3 (4): 269–284. doi:10.1002/jcd.3180030404. https://www.dmgordon.org/papers/cover.pdf. 
• Markström, Klas (2009), "Extremal hypergraphs and bounds for the Turán density of the 4-uniform K5", Discrete Mathematics 309 (16): 5231–5234, doi:10.1016/j.disc.2009.03.035 
• Sidorenko, A. (1995), "What we know and what we do not know about Turán numbers", Graphs and Combinatorics 11 (2): 179–199, doi:10.1007/BF01929486 
• Sidorenko, Alexander (2021), "On Turán numbers of the complete 4-graphs", Discrete Mathematics 344 (11), doi:10.1016/j.disc.2021.112544 
• Turán, P (1941), "Egy gráfelméleti szélsőértékfeladatról (Hungarian. An extremal problem in graph theory.)" (in Hungarian), Mat. Fiz. Lapok 48: 436–452 
• Turán, P. (1961), "Research problems", Magyar Tud. Akad. Mat. Kutato Int. Közl. 6: 417–423