大家好，我是大老李，這期節(jié)目讓我們在質(zhì)數(shù)話題中插播一則新聞，它有關(guān)數(shù)學家在圖論領(lǐng)域里的一個發(fā)現(xiàn)。在今年9月，俄羅斯數(shù)學家雅羅索夫·什托夫（Yaroslav Shitov ）發(fā)表了一篇僅三頁的論文，論文中，其發(fā)現(xiàn)了一個有53年歷史的圖論領(lǐng)域中的猜想的反例，從而推翻推翻了這一猜想，這個猜想名為：斯蒂芬·赫德涅米猜想（Stephen Hedetniemi conjecture）。

要理解這個猜想，需要了解兩個概念，圖的“最小著色數(shù)”和圖的“張量積”(Tensor Product)。這兩個名詞聽上去很高大上，其實說清楚不難。

數(shù)學里的“圖”就是一些點和一些連接點的線。這里點的位置，線的形狀長度等等完全不考慮，只考慮點和線的連接關(guān)系。而兩個點之間的連線稱為“邊”，兩個點之間有一條邊相連稱為“相鄰”。

（圖論中的一張“圖”：僅考慮點和連線關(guān)系）

圖的著色問題，了解“四色定理”的聽眾應(yīng)該也很熟悉了，就是對一幅圖中的點進行著色，要求相鄰的兩個的兩個點的顏色不同?！八纳ɡ怼笔钦f對平面圖，至多四種顏色著色就夠了?！捌矫鎴D”就是那種可以“攤平”，使得所有邊可以不交叉的圖，那種圖，最多用四種顏色就可以著色，使相鄰兩點的顏色都不同，這就是“四色定理”。當然，對非平面圖，你需要的顏色更多。

(“平面圖”是那種沒有邊相交的圖。上圖中的左圖是平面圖，因其可以轉(zhuǎn)化為右圖，使得沒有邊相交)

“圖的最小著色數(shù)”的意思就是，對一幅圖最少需要幾種顏色著色，可以使任何相鄰兩點的顏色不同，這個顏色種類數(shù)量，就是圖的“最小著色數(shù)”。

再講一下圖的張量積，其實也不難理解，就是定義了一種兩幅圖的“乘法”，圖與圖乘起來得到另一張圖。這種乘法的定義我們借助一道“應(yīng)用題”來理解：

假設(shè)大老李要搞一次相親會，大老李認識一些單身男性朋友。大老李的太太也認識一些單身女性朋友，所以大老李想把他們集中在一起，搞一次相親會。

在相親會中，大老李設(shè)計了一個游戲環(huán)節(jié)，是4人一組，兩男兩女參加。但是我知道我認識的那些男性朋友有些是互相認識的，我太太認識的女性朋友，有些也是互相認識的。游戲時，我希望參加的兩位男士是互相認識的，兩位女士也互相認識，這樣玩游戲氣氛更輕松熱烈點。

到底我邀請的那些參加相親會的朋友能否滿足這樣的分組條件呢？當然，這里假設(shè)參會的男女人數(shù)相等，而且都是偶數(shù)。

那這道題我可以這樣解決，我先把參會的男性用一個點表示，兩人如果相識則連一條線。這樣得到一張男性朋友關(guān)系圖。同樣方法可以畫出女性朋友關(guān)系圖。

然后，我要參考這對兩張圖進行一個操作，得到一張新的圖。操作方法如下：將所有男性朋友女性朋友可能兩兩組合，組成一對，在新的圖中作為一個點表示，每個人可以重復(fù)組合出現(xiàn)。

比如，如果原來有a個男性和a個女性，那么根據(jù)簡單的組合算法，新的圖就會有a^2個點，每個點代表一對可能的組合。

然后，我要給這些點之間連線，連線規(guī)則是：取兩個點，分別考察每個點所代表的組合對中的男性和女性。如果這兩個男性和女性在原先的圖中之間有連線，則把這兩個點連一條線，否則不連線。舉個例子就明白。

比如，如果我邀請參加相親會的男性是哈利波特，羅恩，馬爾福；女性方面是：赫敏，金妮，張秋。

(大老李邀請的男女朋友關(guān)系示意圖)

那如果有一個點是表示的是哈利波特，金妮；另一個點表示的羅恩和赫敏，那么你需要把它們之間連條線，因為哈利波特和羅恩，以及赫敏與金妮算是好朋友。如果有一個點是表示的是哈利波特和張秋；另一個點表示馬爾福和金妮，那么就不連線，因為哈利波特與馬爾?？隙ú皇呛门笥眩瑥埱锱c金妮也沒啥交集?？傊?，新的圖中點要連線的話，要求就是在老的圖中，對應(yīng)點也有連線。

另外說明一點，自己與自己不需要連線，比如“哈利波特-赫敏”與“哈利波特-金妮”之間就不用連線了。

(根據(jù)前面的關(guān)系圖求得的張量積圖，它斷開成了兩部分)

以上我們就定義了一種從兩張圖進行一種組合，得到新的一張圖的運算，數(shù)學里稱這種運算叫“張量積”，聽我這么一解釋是不是也很簡單。其實叫它“積”是有點道理的，至少你能看到新的圖的點數(shù)是老的兩張圖的點數(shù)之積。

而對我來說，如果我能根據(jù)邀請來的男性和女性朋友關(guān)系圖，求得一張張量積的圖，那我知道，在這張張量積的圖中，任意一條線段兩端所代表的兩男兩女是適合才加這個相親游戲的。當然，這個方法也許很笨，但至少說明了什么是圖的張量積，后面我有時會簡稱為兩張圖的“積”。

另外，在數(shù)學中的張量積并不要求參與運算的兩張圖的點數(shù)相等。你也可以去分析張量積的一些性質(zhì)，比如有沒有交換律，結(jié)合律等等。但這都不重要，今天我們要考慮的是兩張圖的最小著色數(shù)與運算后所得的圖的最小著色數(shù)的關(guān)系。

很早以前，數(shù)學家就證明了，兩張圖的積的最小著色數(shù)小于等于原先兩張圖的最小著色數(shù)的較小者。比如，如果原先兩張圖的最小著色數(shù)是4和5，則它們的積的最小著色數(shù)小于等于4。而很多人做了嘗試，發(fā)現(xiàn)“小于”這種情況做不到 ，實驗結(jié)果都是“等于”這種情況。

于是，1966年，當時還在讀博士的斯蒂芬·赫德涅米，現(xiàn)為克萊姆森大學（位于美國卡羅萊納州）教授，在其博士學位論文里作出了一個猜想：圖的張量積的最小著色數(shù)等于原先兩張圖的最小著色數(shù)的最小者，后來被成為：斯蒂芬·赫德涅米猜想。

（斯蒂芬·赫德涅米猜想）

此后50多年里，數(shù)學家沒能找出任何反例，倒是證明了一些比原猜想稍弱的命題，比如有人證明了，如果原先兩張圖中的其中一個的最小著色數(shù)小于等于4，則赫德涅米猜想是正確的。

但是這次，什托夫卻找到了一個赫德涅米猜想的一個反例，即兩個圖的張量積的最小著色數(shù)比原先兩個圖都小。他的基本思路是利用了之前有關(guān)“冪圖”的一個結(jié)論，冪是冪次的冪。就像之前介紹求張量積的運算，如果一個圖G與自身求張量積，那么結(jié)果可以寫成，類似可以有,等等。

但這類說的“冪圖”里的運算，是另一種冪次。它的特點是底數(shù)和指數(shù)都是一個圖。比如有圖G,H，那么和都是一張圖，都叫“冪圖”(Exponential Graph)。冪圖的定義略有點啰嗦，就不在音頻里講了。但是叫它冪圖的肯定是有原因的。比如，如果圖G有a個頂點，圖H有b個頂點，那么這張圖的頂點數(shù)就是。

Exponential Graph / 冪圖 定義：

Given a definition below (source: On Hedetniemi's Conjecture and the color template scheme by C. Tardiff and X Zhu):

The exponential graph?? has all the functions from vertex-set of ?? to that of ?? as vertices and two of these functions ??, ?? ?are joined by an edge if [??(??),??(??)∈??(??)] for all [??,??]∈??(??).

不管怎樣，數(shù)學家之前已經(jīng)證明，一個圖 G與自己的冪圖，比如構(gòu)成的張量積，其最小著色數(shù)必須等于H的最小著色數(shù)。而Shitov構(gòu)造了一個圖G和它的冪圖，使它們的最小著色數(shù)都大于H的最小著色數(shù)。而它們的張量積的最小著色數(shù)又等于H的最小著色數(shù)，所以這就構(gòu)成了赫德涅米猜想的一個反例，從而推翻了這個猜想。

我知道你現(xiàn)在很想看看這個反例到底長啥樣？很遺憾告訴你，這個反例畫不出來，因為太大了。Shitov估計，這個反例的G的頂點數(shù)在左右，而它的冪圖的點數(shù)在左右，所以完全不可能畫出來，但是它確實可以在數(shù)學上用不到3頁紙的篇幅，精確構(gòu)造出來。

我覺得這是數(shù)學中有一個非常好的有關(guān)反例的例子。數(shù)學中有許多猜想，你可以找出許許多多實例代入驗證，都是對的。但是，它卻可以在非常非常遙遠的位置出現(xiàn)一個反例，比如像這個猜想中，反例出現(xiàn)在的位置。

而今天圖論我們也學了點，比如什么是圖的張量積，也許你下次組織相親活動的時候會相當圖的張量積概念。好了，下期再見！

https://zh.wikipedia.org/zh-cn/%E5%BC%A0%E9%87%8F%E7%A7%AF

https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/

https://arxiv.org/abs/1905.02167

https://math.stackexchange.com/questions/524183/example-of-exponential-graph

https://en.wikipedia.org/wiki/Tensor_product_of_graphs#/media/File:Graph-tensor-product.svg