크네저 그래프

크네저 그래프
크네저 그래프
	Kneser 그래프 K(5, 2); 피터슨 그래프와 이형화된
이름을 따서 명명됨	마틴 크네저
정점
가장자리
색수
특성.	- ) - 정규 분포; 호 변환의
표기법	K(n, k), KGn,k.
	그래프 및 모수 표

그래프 이론에서 Kneser 그래프 K $(n,$ $k)$ (대안 $KG n, k$ )는 정점이 $n$ 원소 집합의 k-element 하위 집합에 해당하고, 해당 두 집합이 분리된 경우에만 두 정점이 인접한 그래프다.크네저 그래프는 1956년에 처음 조사한 마틴 크네저의 이름을 따서 명명되었다.

예

크네저

그래프 4

O = K

(7,

3)

Kneser 그래프 $K (n, 1$ )는 $정점$ 에 대한 전체 그래프 입니다.

Kneser 그래프 $K (n,$ 2)는 $정점$ 에 있는 전체 그래프의 선 그래프를 보완한 것이다.

Kneser 그래프 $K$ ( $2n$ - 1 $,$ $n$ - $1)$ 는 홀수 그래프 $O$ 이며_n, $특히 3$ O = $K (5,$ 2)는Petersen 그래프(오른쪽 위 그림 참조)이다.

Kneser 그래프 $O 4$ = K $(7,$ 3)는 오른쪽에 시각화되었다 $.$

특성.

기본 속성

Kneser 그래프 $K (n,$ $k)$ 에는 ${\tbinom {n}{k}}$ ( ${\tbinom {n}{k}}$ ${\tbinom {n}{k}}$ ) ${\$ 개의 ${\tbinom {n}{k}}$ 정점이 있다.각 꼭지점에는 정확히 ${\tbinom {n-k}{k}}$ ( ${\tbinom {n-k}{k}}$ - $){\$ 개의 인접 ${\tbinom {n-k}{k}}$ 항목이 있다.

Kneser 그래프는 정점 전이적이고 호 전이적이다.단, 비인접 정점 쌍은 해당 집합 쌍의 교차점 크기에 따라 공통 이웃의 수가 다르기 때문에 일반적으로는 강하게 정규 그래프가 아니다.

Kneser 그래프는 정규적이고 에지 변환성이 있기 때문에 연결이 끊긴 $K (2k,$ $k)$ 를 제외하고 정점 연결은 그 정도와 동일하다.보다 정확히 말하면 $K (n,$ $k)$ 의 연결은 ${\tbinom {n-k}{k}},$ ( ${\tbinom {n-k}{k}},$ - ${\tbinom {n-k}{k}},$ ) ${\tbinom {n-k}{k}},$ , ${\tbinom {n-k}{k}},$ 꼭지점당 이웃의 수와 동일하다 ${\tbinom {n-k}{k}},$ (Watkins 1970).

색수

Kneser(1956)의 추측대로, $n\geq 2k$ 2 k $n\geq 2k$ {\ $displaystyle n\geq 2k}$ 에 대한 Kneser 그래프 K $(n$ , k $)$ 의 색수는 $정확히$ n - $2k$ + $2$ 이다 $n\geq 2k$ . 예를 들어, Petersen 그래프는 적절한 색상에 세 가지 색상이 필요하다.이 추측은 여러 가지 방법으로 증명되었다.

라슬로 로바스(1978)는 위상학적 방법을 사용하여 이것을 증명하여 위상학적 결합의 분야를 일으켰다.
곧이어 임레 바라니(1978년)는 보르수크-을 이용해 간단한 증거를 제시했다.울람 정리 및 데이비드 게일의 보조정리.
조슈아 E.그린(2002)은 더 단순하지만 여전히 위상적인 증거로 모건상을 수상했다.
지지 마투셰크(2004)는 순전히 결합적인 증거를 찾아냈다.

$n<2k$ < $n<2k$ $n<2k$ $n<2k$ 일 때 $n<2k$ $K (n,$ $k)$ 의 색수는 1이다.

해밀턴 사이클

Kneser 그래프 $K (n,$ $k)$ 는 다음과 같은 경우 해밀턴 사이클을 포함한다.

n\geq {1}{1}{1}:{2}}\왼쪽(3k+1+{\sqrt{5k^{2}-2k+1}\오른쪽).

이후

{\frac {1}{1}:{2}}:\좌측(3k+1++{5k^{2}-2k+1}\우측)<\좌측\frac {3+{\sqrt{5}{2}}\우측)k+1,},

이 조건은 다음과 같은 경우에 모두 충족된다.

n\geq \left\frac {3+{\sqrt{5}}{2}}\\오른쪽)k+1\약 2.62k+1.

Kneser 그래프 $K (n,$ $k)$ 는 $n=2k+2^{a}$ = $n=2k+2^{a}$ + 2 $n=2k+2^{a}$ ${\$ 와 같은 음이 아닌 정수가 존재하는 경우 해밀턴 사이클을 포함한다.특히 홀수 그래프 $O$ 는_n $n$ ≥ $4일$ 경우 해밀턴 사이클을 가진다.

피터슨 그래프를 제외하고, $n$ ≤ $27$ 과 연결된 Kneser 그래프 K $(n,$ $k)$ 는 모두 해밀턴 그래프(Shields 2004)이다.

클릭

$n$ < $3k일$ 때 Kneser 그래프 $K (n,$ $k)$ 는 삼각형을 포함하지 않는다.보다 일반적으로, $n$ < $ck$ 는 c $크기$ 의 집단을 포함하지 않는 반면, $n$ < $ck$ 는 c 크기의 집단을 포함하지 않는다.더욱이, Kneser 그래프는 $항상$ 길이 4의 사이클을 포함하지만, $n$ 이 $2k$ 에 가까운 값의 경우 가장 짧은 홀수 사이클은 일정하지 않은 길이를 가질 수 있다(Denley 1997).

지름

연결된 Kneser 그래프 $K (n,$ $k)$ 의 직경은 (Valencia-Pabon & Vera 2005):

\왼쪽\lceil {\frac {k-1}{n-2k}\오른쪽\rceil +1}

스펙트럼

Kneser 그래프 $K (n,$ $k)$ 의 스펙트럼은 k + 1 고유값으로 구성된다.

\lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots,k.

j>0

\lambda _{0}

\lambda _{j}

{\

는

\lambda _{j}

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

j>0

다중성

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

j

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

)

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

-

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

(

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

{\tbinom {n}{j}}-{\tbinom {n}{j-1}}

- 1

){\

{

n}{

j-1}}}

는 j

j>0

>

j>0

{\

에 다중성 1이 있다

\lambda _{0}

.증거를 보려면 이 종이를 보아라.

독립번호

Erdős-Ko-Rado 정리에서는 $n\geq 2k$ $n\geq 2k$ $n\geq 2k$ k $n\geq 2k$ 에 대한 크네세르 그래프 $K$ ( $n,$ $k)$ 의 독립번호는 다음과 $n\geq 2k$ 같이 기술하고 있다.

\alpha(K(n,k))={\binom {n-1}{k-1}

참조

Bárány, Imre (1978), "A short proof of Kneser's conjecture", Journal of Combinatorial Theory, Series A, 25 (3): 325–326, doi:10.1016/0097-3165(78)90023-7, MR 0514626
Chen, Ya-Chen (2003), "Triangle-free Hamiltonian Kneser graphs", Journal of Combinatorial Theory, Series B, 89 (1): 1–16, doi:10.1016/S0095-8956(03)00040-6, MR 1999733
Denley, Tristan (1997), "The odd girth of the generalised Kneser graph", European Journal of Combinatorics, 18 (6): 607–611, doi:10.1006/eujc.1996.0122, MR 1468332
Greene, Joshua E. (2002), "A new short proof of Kneser's conjecture", American Mathematical Monthly, 109 (10): 918–920, doi:10.2307/3072460, JSTOR 3072460, MR 1941810
Kneser, Martin (1956), "Aufgabe 360", Jahresbericht der Deutschen Mathematiker-Vereinigung, 58 (2): 27
Lovász, László (1978), "Kneser's conjecture, chromatic number, and homotopy", Journal of Combinatorial Theory, Series A, 25 (3): 319–324, doi:10.1016/0097-3165(78)90022-5, hdl:10338.dmlcz/126050, MR 0514625
Matoušek, Jiří (2004), "A combinatorial proof of Kneser's conjecture", Combinatorica, 24 (1): 163–170, doi:10.1007/s00493-004-0011-1, hdl:20.500.11850/50671, MR 2057690
Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), "Sparse Kneser graphs are Hamiltonian", STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, New York: ACM, pp. 912–919, arXiv:1711.01636, MR 3826304
Shields, Ian Beaumont (2004), Hamilton Cycle Heuristics in Hard Graphs, Ph.D. thesis, North Carolina State University, archived from the original on 2006-09-17, retrieved 2006-10-01
Simpson, J. E. (1991), "Hamiltonian bipartite graphs", Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium, vol. 85, pp. 97–110, MR 1152123
Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), "On the diameter of Kneser graphs", Discrete Mathematics, 305 (1–3): 383–385, doi:10.1016/j.disc.2005.10.001, MR 2186709
Watkins, Mark E. (1970), "Connectivity of transitive graphs", Journal of Combinatorial Theory, 8: 23–29, doi:10.1016/S0021-9800(70)80005-9, MR 0266804

외부 링크

Weisstein, Eric W. "Kneser Graph". MathWorld.
Weisstein, Eric W. "Odd Graph". MathWorld.

Search

크네저 그래프

네임스페이스

더

목차

예

특성.

기본 속성

색수

해밀턴 사이클

클릭

지름

스펙트럼

독립번호

관련 그래프

참조

외부 링크

크네저 그래프
Kneser 그래프 K $(5,$ 2) 피터슨 그래프와 이형화된
이름을 따서 명명됨	마틴 크네저
정점	${\binom {n}{k}}$
가장자리	${\frac {1}{1}:{2}}: {\binom {n}{k}}{\binom {n-k}{k}}}}$
색수	${\displaysty}n-2k+2&n\geq 2k\\1n<2k\end{case}}}$
특성.	${\tbinom {n-k}{k}}$ - ${\tbinom {n-k}{k}}$ ) ${\$ - 정규 ${\tbinom {n-k}{k}}$ 분포 호 변환의
표기법	$K (n, k), KG n, k$ .
그래프 및 모수 표