투란 수

Turán number

수학에서, 순서 n의 r-균일 하이퍼그래프에 대한 투란 번호 T(n,k,r)는 k 정점의 모든 유도 하위그래프가 가장 작은 r-에지를 포함하도록 하는 r-에지 수가 적다.이 숫자는 turan(1941년)에 의해 r = 2에 대해 결정되었고, 일반 r에 대한 문제는 turan(1961년)에 도입되었다.논문(Sidorenko 1995)은 투란 숫자에 대한 조사를 한다.

정의들

정점 집합 X를 수정한다.주어진 r의 경우, r 에지 또는 블록은 r 정점의 집합이다.X의 모든 k-element 부분집합이 블록을 포함하는 경우 블록 집합을 투란(n,k,r) 시스템(n ≥ k ≥ r)이라고 한다.투란 번호 T(n,k,r)는 그러한 시스템의 최소 규모다.

예

파노 비행기의 선로 보완은 투란 (7,5,4) 계를 형성한다.T(7,5,4) = 7.[1]

다른 조합 설계와의 관계

라는 것을 알 수 있다.

평등은 Steiner 시스템 S(n - k, n - r, n)가 존재하는 경우에만 유지된다.[2]

An (n,r,k,r)-lotto 설계는 (n,k,r)-Turan 시스템이다.따라서 T(n,k, r) = L(n,r,k,r)이다.[3]

참고 항목

참조

  1. ^ Colbourn & Dinitz 2007, 페이지 649, 예 61.3
  2. ^ Colbourn & Dinitz 2007, 페이지 649, Realk 61.4
  3. ^ Colbourn & Dinitz 2007, 513, 발의안 32.12

참고 문헌 목록

  • Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
  • Godbole, A. P. (2001) [1994], "Turán number", Encyclopedia of Mathematics, EMS Press
  • 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
  • Turán, P (1941), "Egy gráfelméleti szélsőértékfeladatról (Hungarian. An extremal problem in graph theory.)", Mat. Fiz. Lapok (in Hungarian), 48: 436–452
  • Turán, P. (1961), "Research problems", Magyar Tud. Akad. Mat. Kutato Int. Közl., 6: 417–423