2025-11-19T18:52:13.613004

On BollobÃ¡s-type theorems of $d$-tuples

Yue

In 1965, BollobÃ¡s proved that for a BollobÃ¡s set-pair system $\{(A_i,B_i)\mid i\in[m]\}$, the maximum value of $\sum_{i=1}^m\binom{|A_i|+|B_i|}{A_i}^{-1}$ is $1$. HegedÃ¼s and Frankl recently extended the concept of BollobÃ¡s systems to $d$-tuples, conjecturing that for a BollobÃ¡s system of $d$-tuples, $\{(A_i^{(1)},\ldots,A_i^{(d)})\mid i\in[m]\}$, the maximum value of $\sum_{i=1}^m\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}^{-1}$ is also $1$. This paper refutes this conjecture and establishes an upper bound for the sum. In the case $d=3$, the derived upper bound is asymptotically tight. Furthermore, we sharpen an inequality for skew BollobÃ¡s systems of $d$-tuples in HegedÃ¼s and Frankl's paper. Finally, we determine the maximum size of a uniform skew BollobÃ¡s system of $d$-tuples on both sets and spaces.

academic

$d$ -원소 조합에 대한 Bollobás 형 정리

기본 정보

논문 ID: 2411.17192
제목: On Bollobás-type theorems of $d$ -tuples
저자: Erfei Yue (헝가리 에트뵈스 로란드 대학교 수학 연구소)
분류: math.CO (조합론)
발표 시간: 2024년 11월 26일 초판 제출, 2024년 12월 30일 3판
논문 링크: https://arxiv.org/abs/2411.17192

초록

본 논문은 $d$ -원소 조합에 대한 Bollobás 형 정리의 확장을 연구한다. 1965년 Bollobás는 Bollobás 집합 쌍 시스템 $\{(A_i,B_i)\mid i\in[m]\}$ 에 대해 $\sum_{i=1}^m\binom{|A_i|+|B_i|}{A_i}^{-1}$ 의 최댓값이 1임을 증명했다. Hegedüs와 Frankl은 최근 Bollobás 시스템의 개념을 $d$ -원소 조합으로 확장하고, $d$ -원소 조합의 Bollobás 시스템 $\{(A_i^{(1)},\ldots,A_i^{(d)})\mid i\in[m]\}$ 에 대해 $\sum_{i=1}^m\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}^{-1}$ 의 최댓값도 1이라고 추측했다. 본 논문은 이 추측을 반박하고, 해당 합의 상한을 확립하며, $d=3$ 인 경우 점근적 타이트성을 증명한다.

연구 배경 및 동기

역사적 배경

Bollobás 형 정리는 1965년 Bollobás가 초그래프 문제를 해결하기 위해 증명한 중요한 결과에서 비롯되었다. 이 정리와 그 확장은 극값 집합론의 핵심 위치를 차지하며 깊은 이론적 의의와 광범위한 응용 가치를 갖는다.

문제의 중요성

이론적 가치: Bollobás 형 정리는 극값 집합론의 기초 도구로서 조합 최적화 및 그래프 이론 문제에 중요한 이론적 지원을 제공한다
광범위한 응용: 자동기계 이론, 대수 조합론, 초그래프 이론 등 여러 분야에서 중요한 응용을 갖는다
확장의 의의: 집합 쌍에서 $d$ -원소 조합으로의 확장은 자연스럽고 중요한 이론 발전 방향이다

기존 방법의 한계

Hegedüs와 Frankl이 제시한 추측(Conjecture 1)은 지나치게 낙관적이며 이원 경우의 결과를 직접 유추한 것이다
$d\geq 3$ 인 경우에 대해 체계적인 이론 분석과 정확한 상한 추정이 부족하다
기존의 확률 방법과 대수 방법은 고차원 경우를 다루기 위해 추가 발전이 필요하다

핵심 기여

Hegedüs-Frankl 추측 반박: 반례(Example 2)를 구성하여 $d$ -원소 조합 Bollobás 시스템에서 해당 합의 최댓값이 1이 아님을 증명했다
새로운 상한 확립: 일반적인 $d$ -원소 조합 Bollobás 시스템에 대해 점근 상한 $\frac{1}{d-1}\binom{n+d-2}{d-2}+O(n^{d-3})$ 을 제시했다
$d=3$ 경우의 타이트 경계: $d=3$ 일 때 상한 $\frac{n+3}{2}$ 가 점근적으로 타이트함을 증명했다
기울어진 Bollobás 시스템 부등식 개선: Hegedüs-Frankl의 결과를 더 정확한 형태로 개선했다(Theorem 1.8)
균등 경우의 정확한 경계 결정: 균등 기울어진 Bollobás 시스템에 대해 집합 및 벡터 공간 경우 모두에서 정확한 최대 규모를 제시했다

방법론 상세 설명

핵심 개념 정의

Bollobás 시스템( $d$ -원소 조합 버전): $F = \{(A_i^{(1)}, \ldots, A_i^{(d)}) \mid i \in [m]\}$ 이 $d$ -원소 조합의 집합이고, 모든 $i \in [m]$ 과 $p \neq q$ 에 대해 $A_i^{(p)} \cap A_i^{(q)} = \emptyset$ 이며, 모든 $i \neq j$ 에 대해 $p < q$ 가 존재하여 $A_i^{(p)} \cap A_j^{(q)} \neq \emptyset$ 이면 $F$ 를 Bollobás 시스템이라 한다.

기울어진 Bollobás 시스템: 조건 " $i \neq j$ "를 " $i < j$ "로 변경하면 기울어진 Bollobás 시스템의 정의를 얻는다.

주요 기술 방법

1. 확률 방법 (Probabilistic Method)

핵심 아이디어: 무작위 순열을 이용하여 서로 다른 원소 조합 간의 교집합 성질을 분석한다.

Theorem 1.6과 1.8의 증명에서 저자는 다음의 확률론적 논증을 채택했다:

무작위 순열 $\sigma \in S_{n+d-1}$ 선택
$\{n+1, \ldots, n+d-1\}$ 을 분리자로 사용
사건 $E_i$ 를 원소 조합 $(A_i^{(1)}, \ldots, A_i^{(d)})$ 의 원소들이 특정 순서로 배열되는 것으로 정의
확률 $P(E_i) = \left(\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|+d-1}{d-1}\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}\right)^{-1}$ 계산

핵심 통찰: 서로 다른 사건 $E_i$ 와 $E_j$ ( $i \neq j$ )는 동시에 발생할 수 없다. 이는 Bollobás 시스템의 교집합 조건이 모순을 야기하기 때문이다.

2. 외적 대수 방법 (Exterior Algebra Method)

벡터 공간 위의 Bollobás 시스템을 다루기 위해 사용된다(Theorem 1.13).

핵심 도구:

외적(쐐기곱): $\alpha_1 \wedge \cdots \wedge \alpha_k$
선형 독립성 판정: $\alpha_1, \ldots, \alpha_k$ 가 선형 독립 ⟺ $\alpha_1 \wedge \cdots \wedge \alpha_k \neq 0$

증명 전략:

일반적 위치 논증(Lemma 3.3)을 이용하여 적절한 선형 사상 $\phi_k: V \to V_k$ 구성
선형 범함수 $f_i$ 를 정의하여 $f_i(\xi_i) \neq 0$ 이고 $f_i(\xi_j) = 0$ ( $i < j$ 일 때)이 되도록 함
$f_1, \ldots, f_m$ 이 선형 독립임을 증명하여 규모 상한 도출

3. 귀납법

일반적 $d$ 에 대해 수학적 귀납법을 확률론적 논증과 결합하여 재귀 관계식을 확립한다.

반례 구성

Example 2의 정교한 설계: $d=3$ 에 대해 족 $F = \bigcup_{l=0}^{\lfloor n/2 \rfloor} F_l$ 을 구성하며, 여기서 $F_l$ 은 $(l, n-2l, l)$ 형태의 모든 서로소 삼원조를 포함한다.

주요 성질:

Bollobás 시스템의 정의를 만족한다
해당 합의 값은 $\lfloor n/2 \rfloor + 1$ 로 추측의 상한 1보다 훨씬 크다
저자가 증명한 상한 $\frac{n+3}{2}$ 에 가까우며 상한의 타이트성을 보여준다

실험 결과

주요 이론 결과

Theorem 1.6 (Bollobás 시스템의 상한):

$d=3$ : $\sum_{i=1}^m \binom{|A_i^{(1)}|+|A_i^{(2)}|+|A_i^{(3)}|}{|A_i^{(1)}|,|A_i^{(2)}|,|A_i^{(3)}|}^{-1} \leq \frac{n+3}{2}$
일반 $d$ : 상한은 $\frac{1}{d-1}\binom{n+d-2}{d-2} + O(n^{d-3})$

Theorem 1.8 (기울어진 Bollobás 시스템의 개선): $\sum_{i=1}^m \left(\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|+d-1}{d-1}\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}\right)^{-1} \leq 1$