콜린 드 베르디에르 그래프 불변성

콜린 드 베르디에르의 불변제는 1990년 이브 콜린 드 베르디에르가 도입한 모든 그래프 G에 대한$$ 그래프 매개변수 $){\displaystyle \mu(G)}$이다.그것은 특정 슈뢰딩거 운영자의 두 번째 고유값의 최대 다중성에 대한 연구에 의해 동기 부여되었다.^[1]

정의

Let ${\displaystyle G=(V,E)}$ be a loopless simple graph with vertex set ${\displaystyle V=\{1,\dots ,n\}}$. Then ${\displaystyle \mu (G)}$ is the largest corank of any symmetric matrix ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)}}$ such that:

• (M1) for all ${\displaystyle i,j}$ with ${\displaystyle i\neq j}$: ${\displaystyle M_{i,j}<0}$ if ${\displaystyle \{i,j\}\in E}$, and ${\displaystyle M_{i,j}=0}$ if ${\displaystyle \{i,j\}\notin E}$;
• (M2) $M{\displaystyle }$ ${\displaystyle M}$은(는) 정확히 하나의 음의 고유값(다중성 1)을 가지고$$ 있으며,
• (M3) there is no nonzero matrix ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)}}$ such that ${\displaystyle MX=0}$ and such that ${\displaystyle X_{i,j}=0}$ if either ${\displaystyle i=j}$ or ${\displaystyle M_{i,j}\neq 0}$ hold.^[1][2]

알려진 그래프 패밀리의 특성화

잘 알려진 여러 그래프 계열은 콜린 드 베르디에르 불변제 측면에서 다음과 같은 특징을 가질 수 있다.

• G에 에지가 없는 경우에만 μ μs 0;^[1][2]
• G가 선형 숲(경로의 분리합)인 경우에만 μ μ μ ^[1][3]1
• G가 외부 평면인 경우에만 μ≤ 2;^[1][2]
• G가 평면인 경우에만 μ≤ 3;^[1][2]
• G가 R에³ 무연계 임베디드 가능한 경우에만 μ4.^[1][4]

이러한 동일한 그래프 계열은 그래프의 콜린 드 베르디에르 불변성 그래프와 그 보완 구조의 연결에도 나타난다.

• n-vertex 그래프의 보수가 선형 숲이면 μ μ n - 3;^[1][5]
• n-vertex 그래프의 보수가 외부 평면인 경우 μ μ n - 4;^[1][5]
• n-vertex 그래프의 보수가 평면이면 μ μ n - 5이다.^[1][5]

그래프 마이너

그래프의 부차는 가장자리를 수축하고 가장자리와 정점을 삭제하여 그래프에서 형성된 또 다른 그래프다.콜린 드 베르디에르 불변성은 마이너 모노톤으로, 그래프의 마이너만 취하면 불변성을 감소시키거나 그대로 둘 수 있다는 것을 의미한다.

H가 G의 마이너라면 $\mu {\displaystyle }$ (${\displaystyle H}$) μ${\displaystyle \mu }$ (${\displaystyle }$G${\displaystyle }$) ${\displaystyle \mu (H)\leq \mu (G$^[2]

By the Robertson-세이모어 정리, 모든 k에 대해 최대 k에 불변성을 갖는 그래프가 마이너로서 H의 멤버가 없는 그래프와 동일하도록 그래프의 유한 집합 H가 존재한다.콜린 드 베르디에르(1990)는 이러한 금지된 미성년자 집합을 k ≤ 3에 대해 열거하고, k = 4에 대해 금지된 미성년자 집합은 피터슨 계열의 7개의 그래프로 구성되는데, 이는 연결되지 않은 내장형 그래프를 μ ≤ 4의 그래프와 피터슨 계열 부전위가 없는 그래프로 특징화한 두 가지 때문이다.^[4]k = 5의 경우 금지된 미성년자 집합에는 희우드 계열의 그래프 78개가 포함되어 있으며, 더 이상 없을 것으로 추측된다.^[6]

색수

콜린 드 베르디에르(1990)는 콜린 드 베르디에르 불변 μ가 있는 그래프는 최대 μ + 1 색으로 채색될 수 있다고 추측했다.예를 들어, 선형 숲은 불변 1을 가지며, 2색을 가질 수 있고, 외부 평면 그래프는 불변 2색을 가질 수 있으며, 3색을 가질 수 있으며, 평면 그래프는 불변 3색을 가질 수 있으며, (4색 정리 기준) 4색을 가질 수 있다.

콜린 드 베르디에르 불변성 그래프(Colin de Verdiér invariant)가 최대 4개까지 포함된 그래프의 경우, 이러한 추측은 사실이며, 이것들은 연결성이 없는 내장형 그래프이며, 최대 5개의 색수를 가지고 있다는 사실은 K-minor-free₆ 그래프에 대한 해드와이거 추측의 닐 로버트슨, 폴 세이모어, 로빈 토마스(1993)에 의한 증거의 결과물이다.

기타 속성

If a graph has crossing number ${\displaystyle k}$, it has Colin de Verdière invariant at most ${\displaystyle k+3}$. For instance, the two Kuratowski graphs ${\displaystyle K_{5}}$ and ${\displaystyle K_{3,3}}$ can both be drawn with a single crossing, and have Colin de Verdière invariant at most4개의^[2]

영향

콜린 드 베르디에르 불변성은 단일 행렬이 아닌 그래프에 해당하는 행렬의 클래스를 통해 정의된다.같은 선을 따라 다른 그래프 매개변수를 최소 순위, 최소 세미더파인 순위, 최소 스큐 순위 등 동일한 선을 따라 정의하고 연구할 수 있다.

메모들

참조

• 콜린 드 Verdière, 이브(1990년),"수르 unnouvel 고정 데 graphes 것은 un critère 드 planarité"면 필기장이 Combinatorial이론, 시리즈 B50(1):11–21, doi:10.1016(90)90093-F.닐 Calkin에 의해 콜린 드 Verdière, 이브(1993년)," 새로운 그래프 invariant고 평평한 기준에", 로버트슨, 닐에 시모어, 폴(eds.)Graph구조 이론:Proc로 번역을 하다.AMS–IMS–SIAM 합동 하계 연구 회의 Graph미성년자에, 현대 수학, vol. 147, 미국 수학회,를 대신하여 서명함. 137–147.
• van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", Graph Theory and Combinatorial Biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud., vol. 7, Budapest: János Bolyai Math. Soc., pp. 29–85.
• Kotlov, Andrew; Lovász, László; Vempala, Santosh (1997), "The Colin de Verdiere number and sphere representations of a graph", Combinatorica, 17 (4): 483–521, doi:10.1007/BF01195002
• Lovász, László; Schrijver, Alexander (1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs", Proceedings of the American Mathematical Society, 126 (5): 1275–1285, doi:10.1090/S0002-9939-98-04244-0.
• Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwiger's conjecture for K₆-free graphs" (PDF), Combinatorica, 13: 279–361, doi:10.1007/BF01202354, archived from the original (PDF) on 2009-04-10, retrieved 2010-08-06.