https://en.formulasearchengine.com/api.php?action=feedcontributions&feedformat=atom&user=50.46.39.99formulasearchengine - User contributions [en]2026-05-04T05:06:47ZUser contributionsMediaWiki 1.43.0-wmf.28https://en.formulasearchengine.com/index.php?title=Pivotal_altitude&diff=21429Pivotal altitude2012-03-18T21:54:48Z<p>50.46.39.99: </p>
<hr />
<div>In mathematics, the ''' Turán number''' T(''n'',''k'',''r'') for ''r''-uniform [[hypergraph]]s 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''&nbsp;=&nbsp;2 by {{harvtxt|Turán|1941}}, and the problem for general ''r'' was introduced in {{harvtxt|Turán|1961}}. The paper {{harv|Sidorenko|1995}} gives a survey of Turán numbers. ́<br />
<br />
==Definitions==<br />
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'' ≥ ''k'' ≥ ''r'') if every ''k''-element subset of ''X'' contains a block.<br />
The ''' Turán number''' T(''n'',''k'',''r'') is the minimum size of such a system.<br />
<br />
==Example==<br />
The complements of the lines of the [[Fano plane]] form a Turán (7,5,4)-system. T(7,5,4) = 7.<ref>{{harvnb|Colburn|Dinitz|2007|loc=pg. 649, Example 61.3}}</ref><br />
<br />
==Relations to other combinatorial designs==<br />
It can be shown that<br />
::<math>T(n,k,r) \geq \binom{n}{r} {\binom{k}{r}}^{-1}.</math><br />
Equality holds if and only if there exists a [[Steiner system]] S(''n'' - ''k'', ''n'' - ''r'', ''n'').<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg. 649, Remark 61.4}}</ref><br />
<br />
An [[combinatorial design|(''n'',''r'',''k'',''r'')-lotto design]] is an (''n'', ''k'', ''r'')-Turán system. Thus, T(''n'',''k'', ''r'') = L(''n'',''r'',''k'',''r'').<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg. 513, Proposition 32.12}}</ref><br />
<br />
==See also==<br />
*[[Forbidden subgraph problem]]<br />
*[[Combinatorial design]]<br />
<br />
==Notes==<br />
{{reflist}}<br />
<br />
==References==<br />
* {{citation|last1=Colbourn|first1=Charles J.|last2=Dinitz|first2=Jeffrey H.|title=Handbook of Combinatorial Designs|year=2007|publisher=Chapman & Hall/ CRC|location=Boca Raton|isbn=1-58488-506-8|edition=2nd Edition}}<br />
*{{springer|id=T/t120190|first=A.P.|last= Godbole}}<br />
*{{citation|first=A. |last=Sidorenko|title=What we know and what we do not know about Turán numbers|journal= Graphs Combin. |volume= 11 |year=1995|issue=2|pages= 179–199 |doi=10.1007/BF01929486}}<br />
*{{citation|last=Turán|first= P|year=1941|title= Egy gráfelméleti szélsöértékfeladatról (Hungarian. An extremal problem in graph theory.) |journal=Mat. Fiz. Lapok|volume= 48 |pages=436–452 |language= Hungarian}}<br />
*{{citation|last=Turán|first= P.|title= Research problems|journal= Maguar Tud. Akad. Mat. Kutato Int. Közl.|volume=6|pages= 417–423 |year=1961}}<br />
<br />
{{DEFAULTSORT:Turan Number}}<br />
[[Category:Extremal graph theory]]<br />
[[Category:Design theory]]</div>50.46.39.99