극단적 결합기

Extremal combinatorics

극단적 결합학은 결합학의 한 분야로, 그 자체가 수학의 한 부분이다. 극단적 결합학에서는 특정 제한을 충족해야 하는 경우 유한 객체(숫자, 그래프, 벡터, 세트 등)의 집합이 얼마나 크거나 얼마나 작을 수 있는지 연구한다.

극단적 결합론의 많은 부분은 집합의 종류와 관련이 있다; 이것은 극단 집합 이론이라고 불린다. 예를 들어, n-element 집합에서 가장 많은 수의 k-element 하위 집합이 쌍으로 교차할 수 있는가? 다른 하위 집합이 없는 하위 집합 중 가장 많은 하위 집합은? 후자의 문제는 슈페너의 정리에 의해 답되는데, 이는 극단적 집합론의 많은 부분을 낳았다.

다른 종류의 예: 세 사람 중에 서로 아는 사람이 둘, 모르는 사람이 둘인 파티에 몇 명이나 초대할 수 있을까? 램지 이론은 그러한 파티에 적어도 5명이 참석할 수 있다는 것을 보여준다. 또는 0이 아닌 한정된 정수의 집합이 주어지고, 두 개의 표시된 정수의 합을 표시할 수 없다는 제한 하에 가능한 한 이 집합의 부분 집합을 표시하도록 요청된다고 가정합시다. (주어진 정수가 실제로 무엇인지와는 무관하게!) 우리는 항상 그 중 적어도 3분의 1을 표시할 수 있는 것으로 보인다.

참고 항목

참조

  • Jukna, Stasys (2011), Extremal Combinatorics, With Applications in Computer Science, Birkhäuser Verlag, ISBN 3-540-66313-4.