바라나이 정리
Baranyai's theorem결합수학에서 바라나이(Zsolt Baranyai에 의해 증명되고 이름 붙여진)의 정리에서는 완전한 하이퍼그래프의 분해를 다룬다.
정리명세서
결과의 진술은 < > r이(가) 자연수이고 r이 k를 나누면 완전한 하이퍼그래프 k 이(가) 1-요소로 분해된다는 것이다. k}}}는 k 정점을 가진 하이퍼그래프로, 이 하이퍼그래프의 1-요인은 각 정점에 정확히 한 번 닿거나 동등하게 정점의 파티션을 r 크기의 하위 집합으로 접촉하는 혼합형이다.Thus, the theorem states that the k vertices of the hypergraph may be partitioned into subsets of r vertices in different ways, in such a way that each r-element subset appears in exactly one of the partitions.
r= 2 }
In the special case , we have a complete graph on vertices, and we wish to color the edges with colors so that the edges of each color form a perfect matching.Baranyai의 정리에는 n {\}이(가 짝수일 때마다 이것을 할 수 있다고 되어 있다.
역사
r = 2 케이스는 정점 수가 짝수인 모든 전체 그래프에 색의 개수가 같은 가장자리 색상이 있거나 가장자리가 완벽한 일치로 분할될 수 있다는 것을 나타내는 것으로 바꾸어 표현할 수 있다.라운드 로빈 대회 일정을 잡는 데 쓰일 수도 있고, 그 해법은 이미 19세기에 알려져 있었다.k = 2r의 경우도 쉽다.
r = 3 케이스는 R에 의해 확립되었다.1936년 펠테손.일반 사건은 1975년 즈솔트 바라나이(Ssolt Baranyai)에 의해 증명되었다.
참조
- Baranyai, Zs. (1975), "On the factorization of the complete uniform hypergraph", in Hajnal, A.; Rado, R.; Sós, V. T. (eds.), Infinite and Finite Sets, Proc. Coll. Keszthely, 1973, Colloquia Math. Soc. János Bolyai, vol. 10, North-Holland, pp. 91–107.
- van Lint, J. H.; Wilson, R. M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press.
- Peltesohn, R. (1936), Das Turnierproblem für Spiele zu je dreien, Inaugural dissertation, Berlin.