只要你懂joints，joints就會幫助你

新paper上arXiv了https://arxiv.org/abs/2410.06498，這整篇修了一個月，從硬生生從一篇joints paper寫成一篇圖論paper(?)。藉此機會來科普一下我跟眼皮H.-H. H. Yu都在做什麼好了XD

故事要從$n$條直線說起。大家都知道，二維空間中$n$條直線最多交$\binom{n}{2}$個點。那三維空間中的三線交點呢？答案還是$O(n^2)$，因為你可以考慮一個方格跟他的其中一個方向的對角線們。

那讀者就會說啦，年輕人不講武德，說好三維這圖形怎麼是二維的。所以我們就有了以下定義。

定義： 一個joints是三條不共平面的線的交點。

於是我們可以問出一個有意義的問題：

問題： 三維空間中$n$條直線，最多可以交出幾個joints？

(這問題實際上跟Kakeya問題有關，也有更有意義的motivation，但我喜歡把他當成單純點與線的極值問題來看待XD)

實際上，構造並不困難。你考慮$m$個位置足夠任意的平面，兩兩交一條線，三三交一個點，而每個點都在三條線上。由於選的平面足夠任意，這三條線不會共平面。所以我們就有$\binom{m}{2}$條線與$\binom{m}{3}$個joints。也就是說joints個數有$\Omega(n^{3/2})$這麼多個。

Guth跟Katz在看了Dvir用polynomial method證明了finite field Kakeya後，使用了類似的方法證明了$O(n^{3/2})$是對的。後來眼皮跟Yufei Zhao證明了上述構造up to $(1+o(1))$倍是緊的，而我跟眼皮證明了實際上那就是最好的構造。(參考資料：https://arxiv.org/abs/2307.15380，而這問題也有colorful版本，可以參考我之前的blog post)

聰明的讀者看著這個界，可能會想起一個經典定理：Kruskal–Katona定理。

定理： 一個有$\binom{m}{2}$條邊的簡單圖$G=(V,E)$中，最多有$\binom{m}{3}$個三角形。

於是呢，你猜得沒錯，這個定理是我們joints定理的一個推論。如果我們一樣考慮一堆位置足夠任意的平面，但這次我們只取一部分的點跟線。我們把平面跟$V$中的點一一對應，$E$中的一條邊對應到兩個平面的交集，也就是空間中的一條線，那一個三角形正好對應一個joints。於是呢，在這種特殊的joints構造上的考慮我們的joints定理就會得到Kruskal–Katona定理(更準確地說，是Lov\’asz的版本)。

實際上，我們的定理還有個更強的推論，解決了partial shadow problem。你考慮一個有$\binom{m}{2}$條邊的$(t+2)$-uniform的hypergraph，問說裡面有幾個大小是$t+3$的頂點集包含了至少三條邊，也就是問幾個大小是$t+3$的頂點集包含了以下的圖形，那至多也是$\binom{m}{3}$。這正好證明了一個Bollob\’as跟Eccles提出的猜想(實際上三角形的case是在$m$足夠大的時候有人證了，但我們解決了所有$(d-1)$-uniform $d$-clique)。而證明方法也不難，你考慮在$t+3$維空間進行如上的平面構造(改用超平面)，並投影到三維即可，留給讀者練習(?)

除了一些直線形成的joints之外，人們也考慮了平面之間，或甚至更高維度的joints，例如：你可以問說，六維空間中的一堆二維平面，最多有幾個點落在三個沒有線性關係的平面中？Jonathan Tidor、眼皮、Yufei Zhao給出了這問題的答案的正確order。而一樣的，如果考慮一堆超平面交出來的構造，這類問題都可以對應到如下類型的問題：

固定一個(超)圖$H$。一個$n$條邊的(超)圖，裡面最多有幾個$H$？

但上述所有joints問題對應到的$H$都很特定。另一方面，但純考慮這種圖論問題的話，Fridegut跟Kahn證明了答案的order應該是$n^{\rho^*(H)}$，其中$\rho^*(H)$是$H$的fractional covering number。以下我們用$H=C_5$來舉例：你考慮五條邊每一條都給一個權重，使得每個點上看到的權重都至少是$1$，那總權重的最小可能值就是$C_5$的fractional covering number，而最好的選法是每條邊放$\frac{1}{2}$，所以$C_5$的fractional covering number是$\frac{5}{2}$。

終於可以進到本篇的主題了。人類知道joints，人類知道Friedgut–Kahn，於是：

用上面的想法，你可以定義一個$C_5$-joints如下：我們秉持著圖裡一個頂點對應到一個超平面的想法，所以我們考慮五維空間，這樣五個超平面會交一個點。我們希望有五條邊$(i,i+1),~i\in [5]$，也就是我們要五個三維平面，分別是第$i$跟$i+1$個超平面的交集。換句話說，你可以找到五個方向(分別對應到五取四個超平面的交集)使得第$i+2, i+3, i+4$個方向span出的三維空間在我們給定的三維平面集合內。然後我們就可以問以下問題。

問題： 五維空間中$n$個三維平面，最多可以交出幾個$C_5$-joints？

我們最新的paper證明了答案的order也是$n^{5/2}$(一般來說是$n^{\rho^*(H)}$)。而類似上面partial shadow problem，我們可以把$C_5$所有邊同時加$t$頂點，令得到的圖是$\mathcal{C}_t(C_5)$。如果你問說一個$n$條邊的超圖最多有幾個$t+5$個頂點的集合包含了$\mathcal{C}_t(C_5)$，那答案是$cn^{5/2}$，重點是這個$c$跟$t$無關，只取決於我們起始點是$C_5$，我們稱這個現象為partial shadow phenomenon。

此外，在我們的證明過程中，我們還證明了一個關於entropy的不等式，且他是Shearer’s不等式的推廣，於是我們稱它為geometric Shearer’s inequality。(詳情請讀我們的paper XD)

雖然整篇paper的證明都是建立在polynomial method上，但我們試圖把所有多項式的部分塞在一個章節，讓整篇paper對於圖論人類更佳友善。簡而言之，該讀了吧XD