2025-11-25T13:16:17.951447

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Pikhurko, Sun
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge 2$. The value of the limit is currently known for $k\in \{2,3,4,5,6,7\}$ due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we consider the case $k=8$, determining the value of the limit for each $r\ge 4$ and presenting a lower bound for $k=3$ that we conjecture to be sharp.
academic

Brown-Erdős-Sós 문제의 이차 8-간선 경우에 관하여

기본 정보

  • 논문 ID: 2506.01739
  • 제목: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • 저자: Oleg Pikhurko, Shumin Sun (University of Warwick)
  • 분류: math.CO (조합론)
  • 발표 시간: 2025년 10월 16일 (arXiv 버전 2)
  • 논문 링크: https://arxiv.org/abs/2506.01739

초록

본 논문은 Brown-Erdős-Sós 문제의 이차 8-간선 경우를 연구한다. f(r)(n;s,k)f^{(r)}(n;s,k)를 nn개의 정점을 가진 rr-균일 초그래프에서 kk개의 간선을 포함하지 않으면서 이 간선들이 최대 ss개의 정점을 덮는 최대 간선 수로 정의하자. Brown, Erdős, Sós는 1973년에 모든 kk에 대해 극한 lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)이 존재한다고 추측했다. 최근 Delcourt와 Postle이 이 추측을 해결했으며, Shangguan이 모든 균일성 r≥4r\ge 4로 일반화했다. 본 논문은 k=8k=8인 경우를 고려하여 각 r≥4r\ge 4에 대한 극한값을 결정하고 r=3r=3일 때의 하한을 제시한다.

연구 배경 및 동기

  1. 핵심 문제: Brown-Erdős-Sós 문제는 rr-균일 초그래프의 Turán 수를 연구하며, 특정 금지된 부분그래프를 피하는 조건 하에서 nn개의 정점을 가진 초그래프가 포함할 수 있는 최대 간선 수를 다룬다.
  2. 문제의 중요성: 이는 극값 조합론의 기초 문제 중 하나이며, Ramsey 이론, Turán 이론 등 핵심 분야와 밀접한 관련이 있다. 이 문제의 해결은 초그래프의 구조적 성질을 이해하는 데 중요한 의미를 갖는다.
  3. 기존 진전:
    • Brown, Erdős, Sós는 f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t)를 증명했으며, 여기서 t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • t=2t=2일 때 (즉, s=rk−2k+2s = rk-2k+2), 극한 π(r,k):=lim⁡n→∞n−2f(r)(n;rk−2k+2,k)\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k)의 존재성이 증명됨
    • k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\}에 대해 극한값이 알려짐
  4. 연구 동기: k=8k=8은 다음의 자연스러운 연구 대상이며, 이 경우는 특히 r=3r=3과 r≥4r\ge 4일 때 다른 행동을 보이는 새로운 복잡성을 나타낸다.

핵심 기여

  1. 주요 정리: 모든 r≥4r \geq 4에 대해 π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}을 결정함
  2. 하한 결과: π(3,8)≥316\pi(3,8) \geq \frac{3}{16}을 증명하고, 이 하한이 타이트하다고 추측함
  3. 구성 방법: 사영 평면의 관계 그래프를 기반으로 하한을 달성하는 명시적 구성을 제공함
  4. 구조 분석: G8(r)G^{(r)}_8-자유 초그래프의 구조를 깊이 있게 분석하며, 특히 2-클러스터의 분류를 수행함
  5. 응용: 일반화된 Ramsey 수와의 연결을 확립하여 lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12}를 얻음

방법론 상세 설명

문제 정의

k=8k=8일 때 함수 f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k)의 점근 행동을 연구하며, 즉 극한 π(r,8)=lim⁡n→∞n−2f(r)(n;8r−14,8)\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8)의 값을 결정한다.

하한 구성 방법

기본 구성 단위

  • R-그래프: 5개 정점과 3개 간선을 가진 3-그래프로, 한 간선 abcabc와 다이아몬드 {buv,cuv}\{buv, cuv\}로 구성됨
  • 경로 족: Desarguesian 사영 평면을 이용하여 2-경로 족 PP를 구성하며, 특정의 희소성과 연결성 조건을 만족함

확률적 삭제 방법

  1. 사영 평면의 관계 그래프에서 시작하여 이분 그래프 G′G'을 구성
  2. 확률 (logm)/m1/2(log m)/m^{1/2}로 2-경로를 무작위 선택
  3. 확률적 삭제 방법을 사용하여 밀집 구성을 형성하는 경로 제거
  4. 각 2-경로 위에 RR-그래프의 사본 배치

핵심 보조정리

보조정리 3.2: 충분히 큰 소수 거듭제곱 qq에 대해, 다음을 만족하는 2-경로 족 PP가 존재한다:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • 합집합 ⋃P∈PP\bigcup_{P\in P} P는 O(m3/2)O(m^{3/2})개의 간선을 가짐
  • 합집합은 삼각형, 4-사이클, 5-사이클이 없음
  • 임의의 i∈[8]i \in [8]에 대해, 각 ii-부분집합의 정점 수는 최소 i+2i+2

상한 증명 방법

병합 전략

  1. 1-병합: 간선 집합을 연결된 1-클러스터(실제로는 트리)로 분할
  2. 2-병합: {1}∣{2}\{1\}|\{2\}-병합 가능 조건을 통해 2-클러스터로 추가 병합

구조 분석

보조정리 4.7: ∣F∣≥9|F| \geq 9인 임의의 2-클러스터 FF에 대해, FF는 다음 족 중 하나에 속한다:

  • AA: (5,2,2)(5,2,2) 조합의 9-간선 2-클러스터
  • BB: (1,2,4,2)(1,2,4,2) 조합의 9-간선 2-클러스터
  • C1,C2C_1, C_2: 다른 조합의 2-클러스터
  • E,FE, F: 특수 구조의 2-클러스터
  • SiS_i: 1개의 1-트리와 ii개의 다이아몬드로 구성된 (2i+1)(2i+1)-간선 2-클러스터

가중치 할당

r≥5r \geq 5와 r=4r = 4에 대해 다른 가중치 함수를 사용:

r≥5r \geq 5일 때:

1 & \text{if } 1 \in C_F(uv) \\ 1/3 & \text{if } 2 \in C_F(uv) \text{ and } 1 \notin C_F(uv) \\ 0 & \text{otherwise} \end{cases}$$ **$r = 4$일 때**: 5개의 보조 함수 $h_i^F$의 최댓값을 가중치로 사용. ## 실험 설정 본 논문은 순수 이론 연구이며 계산 실험을 포함하지 않는다. 모든 결과는 엄격한 수학적 증명을 통해 얻어진다. ### 증명 검증 - 하한은 명시적 구성으로 검증됨 - 상한은 철저한 경우 분석과 가중치 할당 방법으로 증명됨 - 모든 핵심 보조정리는 완전한 수학적 증명을 포함함 ## 실험 결과 ### 주요 결과 **정리 1.1**: 각 $r \geq 4$에 대해 $\pi(r,8) = \frac{1}{r^2-r}$이다. **정리 1.2**: $\pi(3,8) \geq \frac{3}{16}$이다. **추측 1.3**: $\pi(3,8) = \frac{3}{16}$이다. ### 알려진 결과와의 비교 - $\pi(r,2) = \frac{1}{r^2-r}$ (Rödl) - $\pi(r,4) = \frac{1}{r^2-r}$ (Glock 등) - $\pi(r,6) = \frac{1}{r^2-r}$ for $r \geq 4$ (Glock 등) - $\pi(3,6) = \frac{61}{330}$ (특수한 경우) ### 새로운 발견 1. **임계값 현상**: $r=4$는 $\pi(r,8) = \frac{1}{r^2-r}$이 성립하는 최소 균일성 2. **구조 복잡성**: $k=8$의 경우는 이전에 연구된 $k$ 값들보다 더 복잡한 2-클러스터 구조를 보임 3. **Ramsey 연결**: 일반화된 Ramsey 수와의 새로운 연결 확립 ## 관련 연구 ### 역사적 발전 1. **Brown-Erdős-Sós (1973)**: 원래 추측과 기본 경계 제시 2. **Rödl (1985)**: $k=2$의 경우 해결 3. **Glock (2019)**: $k=3$의 경우 해결 4. **Delcourt-Postle (2024)**: 극한 존재성 증명 5. **Shangguan (2023)**: 모든 균일성으로 일반화 ### 기술적 발전 - **충돌 무관 매칭 이론**: Delcourt-Postle과 Glock 등이 개발한 핵심 기술 - **가중치 할당 방법**: Glock 등의 작업을 기반으로 발전된 상한 기술 - **확률적 구성**: 대수 기하학적 구조를 기반으로 한 확률 방법 ## 결론 및 논의 ### 주요 결론 1. $r \geq 4$일 때 $\pi(r,8)$의 값을 완전히 결정함 2. $r=3$의 경우에 대해 가능하면 최적인 경계를 제공함 3. 일반화된 Ramsey 수와의 새로운 연결 확립 ### 제한사항 1. **$r=3$의 경우**: 하한만 얻어졌으며, 상한 일치는 여전히 미해결 문제 2. **구성 복잡성**: 하한 구성은 상당히 기술적이며, 더 간단한 구성이 존재할 수 있음 3. **일반화**: 방법이 더 큰 $k$ 값에 대한 적용 가능성이 불명확함 ### 향후 방향 1. $\pi(3,8) = \frac{3}{16}$ 추측 증명 2. $k \geq 9$인 경우 연구 3. 더 일반적인 구성 및 상한 기술 탐색 4. 다른 극값 문제와의 연결 탐구 ## 심층 평가 ### 장점 1. **기술적 혁신**: 새로운 2-클러스터 분류 및 가중치 할당 기술 개발 2. **정교한 구성**: 사영 평면을 기반으로 한 구성은 깊은 기하학적 통찰을 보여줌 3. **완전성**: $r \geq 4$에 대한 완전한 해답 제시 4. **명확한 작성**: 기술적 세부사항이 잘 조직되어 이해하기 쉬움 ### 부족한 점 1. **$r=3$ 불완전성**: 주요 미해결 문제가 여전히 남아있음 2. **방법의 특수성**: 기술이 $k=8$에 매우 특화되어 있어 일반화 가능성이 제한적 3. **계산 복잡성**: 일부 증명 과정이 상당히 길고 기술적임 ### 영향력 1. **이론적 기여**: Brown-Erdős-Sós 문제 연구 진전 2. **방법론**: 유사한 문제에 대한 새로운 기술 도구 제공 3. **응용 가치**: Ramsey 이론과의 연결이 새로운 연구 방향 개척 ### 적용 가능 분야 이 방법은 다음에 적용 가능: 1. 초그래프 극값 문제 연구 2. 금지된 부분그래프의 Turán 형 문제 3. 조합 최적화의 구조 분석 4. 대수 조합론의 응용 ## 참고문헌 논문은 해당 분야의 핵심 문헌을 인용하며, 다음을 포함한다: - Brown, Erdős, Sós의 원래 작업 - Delcourt-Postle의 획기적 결과 - Glock 등의 일련의 작업 - Shangguan의 일반화 결과 - Bennett 등의 일반화된 Ramsey 수에 관한 작업 --- **종합 평가**: 이는 Brown-Erdős-Sós 문제 연구에서 중요한 진전을 이룬 고품질의 이론 조합론 논문이다. 주요 미해결 문제($r=3$의 경우)가 완전히 해결되지는 않았지만, 논문의 기술적 기여와 방법론적 혁신은 이 분야의 후속 연구를 위한 견고한 기초를 마련한다.