Baranyain lause

Baranyai'n lause on lause täydellisten hypergraafien osioista . Zsolt Baranyai on todistanut ja nimetty hänen mukaansa.

Sanamuoto

Jos ovat luonnollisia lukuja ja r jakaa k :n, niin koko hypergraafi voidaan jakaa 1-kertoimeksi . $2\leqslant r<k$ ${\displaystyle K_{r}^{k))$

Muistiinpanot

${\displaystyle K_{r}^{k))$ on hypergraafi, jossa on k pistettä, jossa jokainen r - pisteen osajoukko muodostaa hyperreunan.
Tämän hypergraafin 1-kerroin on joukko hyperreunoja, jotka sisältävät jokaisen kärjen reunoissa täsmälleen kerran, mikä vastaa kärkien jakamista osajoukkoihin, joiden koko on r .

Lause sanoo siis, että hypergrafin k pistettä voidaan jakaa r :n kärjen osajoukkoihin eri tavoin siten, että kukin r -elementtiosajoukko esiintyy osissa täsmälleen kerran. ${\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}$

Case $r = 2$

Erikoistapauksessa meillä on täydellinen graafi , jossa on pisteet ja haluamme värjätä reunat väreillä niin, että kunkin värin reunat muodostavat täydellisen yhteensopivuuden. Baranyain lause sanoo, että voimme tehdä tämän, jos se on parillinen. $r = 2$ $K_n$ $n$ ${\binom {n}{2}}{\frac {2}{n}}=n-1$ $n$

Historia

Tapaus r = 2 voidaan muotoilla uudelleen sanomalla, että millä tahansa täydellä graafilla , jossa on parillinen määrä pisteitä, on reunaväritys , jonka värien lukumäärä on yhtä suuri kuin sen aste , tai vastaavasti, että reunat voidaan hajottaa täydellisiksi yhteensopivuuksiksi . Tätä voidaan käyttää round robin -turnausten luomiseen ja ratkaisu tunnettiin jo 1800-luvulla. Tapaus k = 2 r on myös yksinkertainen.

Tapausta r = 3 tarkasteli vuonna 1963 R. Pelteson. Yleisen tapauksen todisti vuonna 1975 Zsolt Baranyai.

Kirjallisuus

Zsolt Baranyai. Täydellisen yhtenäisen hypergrafin kertoimista // Infinite and Finite Sets, Proc. Coll. Keszthely, 1973 / András Hajnal, Richard Rado, Vera T. Sos. - Pohjois-Hollanti, 1975. - T. 10. - S. 91-107. - (Colloquia Math. Soc. Janos Bolyai). .
Jack van Lint, R.M. Wilson. Kombinatorian kurssi . – 2. - Cambridge University Press , 2001.
Peltesohn R. Das Turnierproblem für Spiele zu je drien. - Berliini, 1936. - ( Alkuväitöskirja ).