수십 년 동안 수학자들은 그래프와 그들이 가진 연결 수에 대한 간단한 질문에 대해 토론했습니다. 이제 학부 수학 학생은 논쟁을 통해 아사프 퍼버 University of California, Irvine 및 마이클 크리 벨레 비치 텔 아비브 대학의 대학은 마침내 증명의 형태로 답을 제공했습니다. XNUMX 월에 게시.

하이파 대학의 수학자 야 이르 카로 (Yair Caro)는“영리하지만 기본적인 논증의 조합으로 충분하다는 것은 적어도 저에게는 약간 놀랍습니다.

그래프는 모서리 (선)로 연결된 정점 (점)의 모음입니다. 수백 년의 연구 끝에 수학자들은 여전히 ​​기본 속성을 조사하고 있습니다. 하나는 그래프 정점의 "패리티"에 관한 것으로, 다른 정점의 홀수 또는 짝수에 연결되어 있는지 여부를 의미합니다.

지난 세기 동안 수학자들은 패리티와 관련된 여러 가지 기본 결과를 입증했습니다. 1960 년대에 Tibor Gallai는 그래프의 정점을 항상 두 그룹 또는 하위 그래프로 분할하여 각 하위 그래프 내의 모든 정점이 서로 짝수로 연결되도록 할 수 있음을 입증했습니다 (그룹 외부의 정점에 대한 연결 무시). ) — 짝수 "도"라고하는 속성.

거의 동시에 그는 그래프의 정점을 두 개의 하위 그래프로 분할하여 한 정점은 모두 짝수이고 다른 정점은 모두 홀수 차수를 가질 수 있음을 관찰했습니다.

그러나 마지막 옵션은 불가능합니다. 각 그래프의 모든 정점이 홀수 차수를 갖도록 모든 그래프를 두 개의 하위 그래프로 분할 할 수있는 방법은 없습니다. 우리는 1730 년대에 아마도 역사상 가장 많은 수학자 인 Leonhard Euler가 정점 그룹이 모두 홀수 차수를 가지면 그룹에 짝수의 정점이 있어야 함을 증명했기 때문에 이것을 알고 있습니다. 그래프의 정점을 두 개의 하위 그래프로 분할하고 각 하위 그래프의 모든 정점이 홀수 차수를 갖는 경우 각 하위 그래프에는 짝수의 정점이 있어야하며 원래 분할되지 않은 그래프는 짝수의 정점 만 가질 수 있습니다 (왜냐하면 두 짝수의 합은 항상 짝수입니다). 즉, 원래 그래프에 홀수의 정점이 있으면 분할을 수행 할 방법이 없습니다.

그래프를 항상 홀수 차수의 두 부분 그래프로 나눌 수 없다는 사실을 감안할 때, 다음 자연적인 질문은 다음과 같습니다. 항상 홀수 차수를 가질 것이라고 확신 할 수있는 그래프에서 꼭짓점의 가장 큰 비율은 얼마입니까?

Krivelevich는 "이상한 일을 할 수 없기 때문에 차선책에 만족해야합니다. 즉, 정점의 상당 부분에 대해 이상한 일을합시다."라고 Krivelevich는 말했습니다.

질문을 확고히하기 위해 간단한 예를 들어 보겠습니다. 삼각형 모양의 세 개의 연결된 정점이있는 그래프입니다. 두 정점을 분리하여 서로 홀수 연결 (1)을 공유하는지 확인할 수 있습니다. 다시 말해, 전체 정점의 XNUMX 분의 XNUMX를 포함하는 삼각형의 하위 그래프를 식별 할 수 있습니다. 여기서 모든 정점의 차수가 홀수입니다.

약 50 년 전 수학자들은 주어진 크기의 그래프에 대해 $ latex frac {1} {2와 같이 전체 그래프에서 전체 정점 수의 일정한 비율을 포함하는 모든 홀수 차수를 가진 하위 그래프가 항상 존재한다고 예측했습니다. } $ 또는 $ latex frac {1} {8} $ 또는 $ latex frac {32} {1,007} $. 그래프에 20 개의 꼭지점이 있든 20 조 개이든 하위 그래프의 크기는 항상 동일한 비율을 충족하거나 초과해야합니다.

"요점은 원래 그래프가 더 커지고 더 커질 수 있으며 여전히 동일한 비율을 유지할 수 있다는 것입니다."라고 Krivelevich는 말했습니다.

그러나 수년 동안 아무도 그러한 특정 비율을 찾을 수 없었습니다. 1990 년대 초에 Caro는 그래프의 크기에 따라 변하는 비율이 아니라 일정한 비율을 발견했습니다. 그는 당신이 가지고 있다면 N 그래프의 정점에는 모든 정점이 홀수 인 $ latex frac {1} {sqrt {N}} $ 이상을 포함하는 하위 그래프가 있습니다. XNUMX 년 후, 알렉스 스콧 이 결과를 $ latex frac {1} {log N} $로 개선했습니다. 이는 Caro의 결과보다 일정한 비율에 훨씬 더 가깝지만 끝이 아닙니다.

“가까웠지만 시가는 없었습니다.”현재 옥스포드 대학의 교수 인 Scott은 말했습니다.

Ferber의 전 대학원 고문 인 Krivelevich가 그를 만나기 위해 캘리포니아를 방문한 30 년 2020 월까지 문제에 대한 진전은 거의 XNUMX 년 동안 시달렸습니다.

Ferber는 최근 동료 중 한 명이 그에게 물었던 접선 관련 질문에 자극을 받아 이상한 그래프에 대한 문제를 다시 검토했습니다. 그는 Krivelevich에 문제를 제기했고 그들은 향후 XNUMX 개월 동안 개발할 전략을 시작했습니다.

이전의 다른 사람들도 따랐던 기본적인 접근 방식은 그래프를 세 가지 유형으로 정렬하는 것이 었습니다. "희소 한"그래프, 몇 개의 다른 정점에 연결된 많은 정점이있는 경우, 단일 정점이 다수에 연결된 "밀집된"그래프 다른 것 (그래프의 총 꼭지점 수에 비례 함), 중간에있는 그래프, 이러한 특성은 없습니다. 1990 년대의 이전 작업은 희박하고 조밀 한 케이스를 이해하기 쉽게 만들었습니다. 가장 어려운 부분은 중간 지점을 이해하는 것이 었습니다.

“문제는 그 사이에 무엇을하고 있는가입니다.”라고 Ferber가 말했습니다.

그들은 그래프가 희박하거나 조밀하지 않은 경우 다른 품질을 가져야한다는 것을 증명할 수있는 절차를 고안했습니다. 즉, 전체 그래프에 비해 조밀하지는 않지만 그 자체로 조밀하고 완전히 연결되지 않은 많은 작은 하위 그래프입니다. 서로에게서. 이 마지막 점을 증명하는 것은 많은 작은 조밀 한 하위 그래프가 서로 연결되어 있지 않다는 것을 프로젝트에서 가장 까다로운 부분 중 하나였습니다.

Ferber는“그들 사이에 가장자리가 없다는 것을 보여주는 것은 상당히 고통 스럽습니다.

Ferber와 Krivelevich는 이러한 많은 작고 조밀 한 하위 그래프를 결합하여 모든 정점이 홀수 인 더 큰 하위 그래프를 만들 수 있음을 확인했습니다. 이제 그들은 모든 가능성 (희소 그래프, 조밀 한 그래프 및 그 사이의 그래프)을 다루었으며 모두 특정 최소 크기의 홀수 하위 그래프를 반드시 포함하고 있음을 보여주었습니다.

2020 년 잘못된 시작 이후 Scott이 피할 수있는 심각한 오류를 알려 주었을 때 Ferber와 Krivelevich는 2021 년 1 월 말에 최종 결과를 게시했습니다. 그들은 모든 그래프에 최소 $ latex frac을 차지하는 하위 그래프가 포함되어 있음을 증명했습니다. 모든 정점이 서로 홀수로 연결되어있는 정점의 {10,000} {XNUMX} $. 마지막으로, 그들은 일정한 분수를 가졌습니다.

(그들이 도달 한 실제 비율은 약간 더 컸지 만 미학적 이유로 $ latex frac {1} {10,000} $로 반올림했습니다. "$ latex frac {1} {9,456} $ 또는 다른 추악한 표현,”Ferber가 말했다.)

여기에서 적어도 두 가지 방법이 있습니다. 첫 번째는 분수를 개선하는 것입니다. 홀수 연결이 있어야하는 정점의 비율이 $ latex frac {1} {10,000} $보다 클 가능성이 매우 높습니다. 1990 년대에 Scott은 $ latex frac {2} {7} $만큼 많을 것이라고 추측했으며 향후 작업이 그 숫자를 추격 할 수 있습니다.

두 번째는이 작업에 이어 새로운 삶을 살았던 관련 질문을 포함합니다.

수학자들은 큰 정점 그룹과 같이 공통적으로 다른 숫자 속성을 가진 정점 모음의 크기를 이해하려고합니다. 이러한 상황이 3 또는 5로 균등하게 나눌 수있는 여러 다른 정점에 연결되어 있지는 않습니다. 단순한 분수도 특징이지만, 홀수 차수를 가진 꼭짓점의 비율이 될 수 있다는 점은 고무적입니다.

"[증거]는 거기에서도 좋은 대답을 기대해야한다고 제안합니다."Scott이 말했습니다.

보정: 2021 년 5 월 19 일
Michael Krivelevich는 2020 년이 아닌 2019 년에 Asaf Ferber와 직접 만났습니다.