헤데트니에미의 추측

그래프 이론에서, 스티븐 T에 의해 공식화된 헤데트니에미의 추측. 1966년 헤데트니에미는 그래프 채색과 그래프의 텐서 곱 사이의 연관성에 관한 것입니다. 이 추측은 다음과 같습니다.

\chi (G\times H)=\min\{\chi (G),\chi (H)\

여기서 $\chi (G)$ χ (G) ${\displaystyle$ \chi (G)}는 무방향 $그래프$ G ${\displaystyle$ G}의 색수를 나타냅니다.

부등식 χ(G × H) ≤ min { χ(G), χ(H)}은 쉽다: G가 k색이면 제품 내 G의 각 복사본에 대해 동일한 색상을 사용하여 G × H를 k색으로 할 수 있고, H가 k색이면 대칭적으로. 따라서, 헤데트니에미의 추측은 텐서 곱이 의외로 적은 수의 색으로 착색될 수 없다는 주장에 해당합니다.

야로슬라프 시토프(2019)에 의해 추측의 반례가 발견되었고(칼라이 2019 참조), 따라서 일반적으로 추측을 반증했습니다.

알려진 사례

비어 있지 않은 간선 집합을 가진 그래프에는 적어도 두 가지 색상이 필요합니다. G와 H가 1색이 아닌 경우, 즉 둘 다 간선을 포함하면, 그들의 곱도 간선을 포함하므로 1색이 아닙니다. 특히, G 또는 H가 이분 그래프일 때, 그 색수가 1 또는 2이기 때문에 이 추측은 사실입니다.

마찬가지로, 두 그래프 G와 H가 2색이 아닌 경우, 즉 이분법이 아닌 경우 둘 다 홀수 길이의 사이클을 포함합니다. 두 홀수 사이클 그래프의 곱은 홀수 사이클을 포함하므로 곱 G × H도 2색이 아닙니다. 즉, G × H가 2색이라면 G와 H 중 적어도 하나는 2색이어야 합니다.

다음 사례는 El-Zahar & Sauer(1985)에 의해 추측이 발표된 지 한참 후에 증명되었습니다. 만약 곱 G × H가 3색이라면, G 또는 H 중 하나도 3색이어야 합니다. 특히, 이 추측은 G 또는 H가 4색일 때마다 사실입니다(이후 불평등 χ(G × H) ≤ min { χ(G), χ(H)}는 G × H가 3색일 때만 엄격할 수 있습니다). 나머지 경우 텐서 곱의 두 그래프 모두 최소 5색이며 매우 제한된 상황에서만 진행되었습니다.

약한 헤데트니에미 추측

다음 함수(Poljak-Rödl 함수라고 함)는 n-색 그래프의 생성물의 색 수가 얼마나 낮을 수 있는지 측정합니다.

f(n)=\min\{\chi(G\times H)\colon \chi(G)=\chi(H)=n\

그렇다면 헤데트니에미의 추측은 $f (n)$ = $n$ 이라고 말하는 것과 같습니다. 약한 헤데트니에미 추측은 대신 함수 f(n)가 무한대라고만 말합니다. 즉, 두 그래프의 텐서 곱이 몇 가지 색상으로 채색될 수 있는 경우, 이는 요인 중 하나의 색수에 대한 어느 정도의 경계를 의미해야 합니다.

Poljak, James H. Schmerl, Zhu에 의해 독립적으로 개선된 (Poljak & Rödl 1981)의 주요 결과는 함수 f(n)가 유계화되면 최대 9로 유계화된다는 것입니다. 따라서 10색 그래프에 대한 헤데트니에미 추측의 증명은 이미 모든 그래프에 대한 약한 헤데트니에미 추측을 의미합니다.

곱셈 그래프

이 추측은 그래프 동형화의 보다 일반적인 맥락에서 연구되는데, 특히 그래프 범주(그래프를 객체로, 동형화를 화살표로 사용)에 대한 흥미로운 관계 때문입니다. 임의의 고정 그래프 K에 대하여, G → K인 K에 동형을 인정하는 그래프 G를 고려합니다. 이들을 K색 그래프라고도 합니다. 이는 일반적인 그래프 채색의 개념을 일반화하는 것인데, 이는 k색이 K색과_k 동일하다는 정의를 기반으로 하기 때문입니다(k개의 정점에서 완전한 그래프로 동형화).

그래프 K는 임의의 그래프 G, H에 대하여 G × H → K가 성립한다는 사실은 G → K 또는 H → K가 성립한다는 것을 의미합니다. 고전적인 채색과 마찬가지로, 역의 의미는 항상 성립합니다: 만약 G(또는 대칭적으로 H)가 K색일 수 있다면, G × H는 H와 독립적으로 동일한 값을 사용함으로써 쉽게 K색이 됩니다. 그러면 헤데트니에미의 추측은 각 완전한 그래프가 곱셈이라는 진술과 같습니다.

위에 알려진 경우는 K₁, K₂, K가₃ 곱셈이라고 말하는 것과 같습니다. K의₄ 경우는 넓게 열려 있습니다. 반면, El-Zahar & Sauer (1985)의 증명은 Hägkvist et al. (1988)에 의해 모든 사이클 그래프가 곱셈적임을 보여주는 일반화되었습니다. 이후, Tardif(2005)는 n/k < 4인 모든 순환클릭 K가_n/k 곱셈적이라는 것을 보다 일반적으로 증명했습니다. 이는 원형 색수 χ의 관점에서 χ $($ $G \timesH)$ < $4$ 이면 χ(G×H) = min { χ(G)}, χ(G)}를 $의미$ 합니다. Wrochna(2017)는 정사각형이 없는 그래프가 곱셈적이라는 것을 보여주었습니다.

비 multiplic 그래프의 예는 동형 순서에서 비교할 수 없는 두 개의 그래프 G와 H로 구성할 수 있습니다(즉, G→H와 H→G 모두 성립하지 않음). 이 경우, K=G×H를 허용하면 G×H→K를 가질 수 있지만, 사영 K→H 또는 K→G로 구성되면 모순이 발생하므로 G와 H 모두 K로 동형화를 허용할 수 없습니다.

지수 그래프

그래프의 텐서 곱은 그래프 범주의 범주 이론적 곱이므로(그래프를 객체로 하고 동형화를 화살표로 함), 추측은 그래프 K와 G에 대한 다음 구성의 관점에서 재구성될 수 있습니다. 지수 그래프 $K$ 는 모든 함수 $V(G)$ → $V(K)$ 를 정점(동형뿐만 아니라)으로 하고 두 개의 함수 f, g가 인접한 그래프입니다.

f(v)는 G의 모든 인접한 정점 v,v'에 대하여 K의 g(v')에 인접합니다.

특히 함수가 G에서 K까지의 동형을 제공하는 경우에만 함수 f(자신과 인접)에 루프가 있습니다. 다르게 보면, 두 함수가 G × K₂ (G의 이분 이중 덮개)에서 K로의 동형을 정의할 때마다 f와 g 사이에 간선이 존재합니다.

지수 그래프는 그래프 범주의 지수 객체입니다. 이는 G × H에서 그래프 K까지의 동형화가 H에서 K까지의^G 동형화에 해당함을 의미합니다. 또한 $eval(v, f)$ = f $(v$ )로 주어진 $G$ × $K$ → $K$ 등의 동형 $평가$ 가 있습니다 $.$ 이러한 성질을 통해 K의 곱셈은 다음과 같다고 결론지을 수 있습니다. (El-Zahar & Sauer 1985)

G 또는 K는 모든 그래프^G G에 대해 K-색상이 가능합니다.

즉, 헤데트니에미의 추측은 지수 그래프에 대한 문장으로 볼 수 있습니다: 모든 정수 k에 대하여 그래프 K가_k^G k색일 수 있거나 또는 루프를 포함하고 있습니다(G는 k색일 수 있음을 의미함). Hedetniemi 추측의 가장 어려운 경우로 동형화 $평가$ : $G$ × $K$ → $K$ 를 볼 수도 있습니다: 만약 곱 G × H가 반례라면, G × K도 반례가 될 것입니다.

일반화

방향 그래프로 일반화된 이 추측은 Poljak & Rödl(1981)에 의해 관찰된 바와 같이 간단한 반례를 가지고 있습니다. 여기서, 방향 그래프의 색수는 기본 그래프의 색수일 뿐이지만, 텐서 곱은 정확히 절반의 에지 수를 갖습니다(G의 방향 에지 g→g' 및 H의 h→h'의 경우, 텐서 곱 G × H는 (g,h)부터 (g,h')까지의 하나의 에지만 갖습니다). 기본 방향이 없는 그래프의 곱은 (g,h')와 (g,h') 사이의 에지를 갖습니다. 그러나 약한 헤데트니에미 추측은 지시된 설정과 지시되지 않은 설정에서 동등한 것으로 밝혀졌습니다(Tardif & Wehlau 2006).

문제를 무한 그래프로 일반화할 수 없습니다. Hajnal(1985)은 두 개의 무한 그래프의 예를 제시했는데, 각각의 그래프는 셀 수 없이 많은 색으로만 색을 칠할 수 있도록, 셀 수 없이 많은 색을 필요로 합니다. Rinot(2013)은 구성 가능한 우주에서 모든 무한 기본 $\kappa$ κ {\displaystyle $\kappa$ \kappa}에 대해 κ $\kappa$ {\displaystyle \kappa}보다 큰 색수의 그래프 쌍이 존재하여 생성물이 여전히 셀 수 없이 많은 색으로만 착색될 수 있음을 증명했습니다.

참고문헌

주출처

Duffus, D.; Sands, B.; Woodrow, R. E. (1985), "On the chromatic number of the product of graphs", Journal of Graph Theory, 9 (4): 487–495, doi:10.1002/jgt.3190090409, MR 0890239.
El-Zahar, M.; Sauer, N. (1985), "The chromatic number of the product of two 4-chromatic graphs is 4", Combinatorica, 5 (2): 121–126, doi:10.1007/BF02579374, MR 0815577, S2CID 7659747.
Häggkvist, R.; Hell, P.; Miller, D. J.; Neumann Lara, V. (1988), "On multiplicative graphs and the product conjecture", Combinatorica, 8 (1): 63–74, doi:10.1007/BF02122553, hdl:1828/1589, MR 0951994, S2CID 39731578.
Hajnal, A. (1985), "The chromatic number of the product of two ℵ₁ chromatic graphs can be countable", Combinatorica, 5 (2): 137–140, doi:10.1007/BF02579376, MR 0815579, S2CID 27087122.
Hedetniemi, S. (1966), Homomorphisms of graphs and automata, Technical Report 03105-44-T, University of Michigan.
Poljak, S.; Rödl, V. (1981), "On the arc-chromatic number of a digraph", Journal of Combinatorial Theory, Series B, 31 (2): 190–198, doi:10.1016/S0095-8956(81)80024-X.
Rinot, A. (2013), Hedetniemi's conjecture for uncountable graphs, arXiv:1307.6841, Bibcode:2013arXiv1307.6841R.
Sabidussi, G. (1957), "Graphs with given group and given graph-theoretical properties", Canadian Journal of Mathematics, 9: 515–525, doi:10.4153/CJM-1957-060-7, MR 0094810, S2CID 124514137.
Shitov, Yaroslav (May 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167.
Tardif, C. (2005), "Multiplicative graphs and semi-lattice endomorphisms in the category of graphs", Journal of Combinatorial Theory, Series B, 95 (2): 338–345, doi:10.1016/j.jctb.2005.06.002.
Tardif, C.; Wehlau, D. (2006), "Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function", Journal of Graph Theory, 51 (1): 33–36, doi:10.1002/jgt.20117, S2CID 17489968.
Wrochna, M. (2017), "Square-free graphs are multiplicative", Journal of Combinatorial Theory, Series B, 122: 479–507, arXiv:1601.04551, doi:10.1016/j.jctb.2016.07.007, S2CID 205930734.

설문조사 및 2차 자료

Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8.
Kalai, Gil (May 10, 2019), "A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi's conjecture", Combinatorics and More.
Klavžar, Sandi (1996), "Coloring graph products: a survey", Discrete Mathematics, 155 (1–3): 135–145, doi:10.1016/0012-365X(94)00377-U, MR 1401366.
Sauer, N. (2001), "Hedetniemi's conjecture: a survey", Discrete Mathematics, 229 (1–3): 261–292, doi:10.1016/S0012-365X(00)00213-2, MR 1815610.
Tardif, Claude (2008), "Hedetniemi's conjecture, 40 years later" (PDF), Graph Theory Notes of New York, 54: 46–57, MR 2445666.
Zhu, Xuding (1998), "A survey on Hedetniemi's conjecture", Taiwanese J. Math., 2 (1): 1–24, doi:10.11650/twjm/1500406890, MR 1609464.

외부 링크

그래프 이론의 돌파구, Numberphile

Search