버르-에르두스 추측

수학에서 Burr-Erdős 추측은 램지 수의 희소성 그래프에 관한 문제였다.이 추측의 이름은 스테판 버스와 폴 에르디스의 이름을 따온 것이며, 에르디스의 이름을 딴 많은 추측들 중 하나이다; 그것은 모든 희박한 그래프 계열의 그래프의 램지 수가 그래프의 정점 수에서 선형적으로 증가해야 한다고 말한다.

그 추측은 이충범에 의해 증명되었다.^[1]

정의들

G가 비방향 그래프인 경우 G의 모든 하위 그래프에 p 이하의 꼭지점이 포함되도록 G의 퇴행성은 최소 숫자 p이다.퇴보 p가 있는 그래프를 p-degenerate라고 한다.마찬가지로 p-감소 그래프(p-degenerate graph)는 도 p 이하의 꼭지점을 반복적으로 제거하여 빈 그래프까지 줄일 수 있는 그래프다.

어떤 그래프 G에 대해서도 최소 $정수{\displaystyle }$ r${\displaystyle }$( G${\displaystyle }$) ${\displaystyle$ r$(G)}$이$($가) 존재한다는 것은 램지의 정리로부터 따르며, 적어도 r${\displaystyle }$( ${\displaystyle G}$) ${\displaysty r(G)}$ 정점에 있는 전체 그래프가 빨간색 또는 파란색인 G의 단색 카피를 포함하도록 한다.예를 들어, 삼각형의 Ramsey 번호는 6이다: 6개의 꼭지점에 있는 완전한 그래프의 가장자리가 어떻게 빨강이나 파랑색이라 할지라도, 항상 빨간 삼각형이나 파란 삼각형이 있다.

추측

1973년 스테판 버르와 폴 에르드스는 다음과 같은 추측을 했다.

모든 정수 p에 대해 상수 c가_p 존재하여, n 꼭지점에 있는 모든 p-degenerate 그래프 G는 최대_p c n의 Ramsey 번호를 갖는다.

즉, n-vertex 그래프 G가 p-degenerate인 경우, c n_p 정점의 모든 2-에지 색상 전체 그래프에 G의 단색 복사본이 존재해야 한다.

알려진 결과

완전한 추측이 증명되기 전에, 그것은 어떤 특별한 경우에 먼저 해결되었다.그것은 Chvátal 외 연구진(1983)에 의해 한계도 그래프로 증명되었다. 그들의 증거는 c의 매우_p 높은 가치로 이어졌다. 그리고 이 상수의 개선은 Eaton(1998년)과 Graham, Rödl & Rucinski(2000년)에 의해 이루어졌다.보다 일반적으로, 이 추정은 경계 최대도가 있는 그래프, 평면 그래프 및 K의_p 하위 구분을 포함하지 않는 그래프를 포함하는 p-arangeable 그래프에 대해 사실인 것으로 알려져 있다.^[2]그것은 또한 두 개의 인접한 정점이 2보다 크지 않은 세분화된 그래프로도 알려져 있다.^[3]

임의 그래프의 경우 램지 번호는 약간만 초선형적으로 성장하는 함수에 의해 경계되는 것으로 알려져 있다.구체적으로, Fox & Sudakov(2009)는 p-degenate n-vertex 그래프 G에 대해 상수 c가_p 존재한다는 것을 보여주었다.

${\displaystyle r(G)\leq 2^{c_{p}{\sqrt {\log n}n.}$

메모들

참조