只要你懂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。