On Alternating 6-Cycles in Edge-Coloured Graphs

想象一下你正身处一场盛大的派对，每个人都穿着红色或蓝色的衬衫。现在，再想象一下在这场派对中，每一对人之间都握过手，而每一次握手要么是“红色握手”，要么是“蓝色握手”。这种混乱且色彩斑斓的连接网络，在数学家眼中被称为“边着色图”（edge-colored graph）。一个让一些好奇的人彻夜难眠的问题是：如果你在这个网络中寻找一种特定的模式——比如一个由六个人组成的圆圈，其握手颜色像红-蓝-红-蓝-红-蓝这样交替出现——你最多能找到多少个这样的模式呢？

这不仅仅是一个派对游戏；它是数学的一个分支，叫做极值组合数学（extremal combinatorics）。它是研究大型系统中模式极限的学科。你可以把它想象成在问：“用砖块搭建墙壁最有效率的方式是什么？”或者“一张纸最多可以折叠多少次？”在这种情况下，“砖块”是握手，而“墙壁”是图的结构。数学家之所以关心这些，是因为理解这些极限有助于我们理解从计算机网络到社会结构中，秩序与混沌是如何相互作用的。有时，看起来最“随机”的排列方式恰恰是创造特定模式最多的方式；而有时，一种非常特定的、有组织的结构才是赢家。弄清楚究竟是哪种情况，就像是在解开一个宇宙级的谜题。

在这篇简短而精炼的笔记中，两位数学家，Hao Chen 和 Jonathan A. Noel，解决了这个谜题中的一个特定部分。他们想知道，在一个巨大的、全连接的派对中，如果每一次握手的颜色都是随机选择红色或蓝色的，那么这种随机的混沌是否是最大化那些交替的六人圆圈（称为交替六循环，alternating 6-cycles）的最佳方式？

长期以来，这一直是一个开放性的问题。虽然他们已经知道了其他形状（如交替路径或长度为四的倍数的循环）的答案，但六循环的情况却是一个顽固的谜团。作者使用了一种强大的数学工具——“旗标代数”（flag algebras）来破解这个密码。你可以把旗标代数想象成一个超强倍率的显微镜，它允许数学家缩放到图的微小部分，计算其中的模式，然后利用这些微小的计数来推导出整个巨大图的样貌。这有点像通过品尝一勺食材的比例，来猜测一锅巨型汤的味道。

论文证明了一个确定的结果：这些交替六循环的最大数量确实是在颜色被完全随机选择时实现的。

结论就在这里：如果你有一个巨大的团（clique，即一个每个人都与其他所有人相连的群体），并且你对连接进行随机着色——即通过抛硬币来决定每一次握手是红色还是蓝色——你将比使用任何其他巧妙的、预先计划好的着色方案获得更多的交替六循环。论文显示，这种随机图中的循环密度正好是 $(1/2)^6$，即 $1/64$。

作者并非仅仅靠猜测，他们提供了严密的证明。他们通过观察一小组六个人（具体来说是一个二部图 $K_{3,3}$）所有可能的着色方式来分解问题。这组六个人的边共有 512 种红蓝着色方式。通过将这 52 种可能性归纳为 26 种独特的“形状”（忽略旋转和翻转），他们得以建立起一个庞大的方程组。

他们引入了一个涉及“旗标”（flags，带有两个特殊“根”顶点的微型图）的巧妙技巧。通过分析这些旗标如何组合在一起，他们构建了一个巨大的 8x8 数字矩阵。这个矩阵充当了一个数学安全网；它是“正半定”的（positive semi-definite），这是一个高级术语，意思是无论你如何在你的巨大图中排列颜色，数学都会迫使交替六循环的数量保持在某个上限之下。当他们计算这些数字时，这个上限正好是 $(1/2)^6$。

因此，这篇论文解决了 Basit 及其同事提出的一个更大问题中的第一个开放案例。它证实了对于这种特定的形状，自然界偏好随机性而非秩序。作者还指出，虽然他们的方法对于这个特定案例非常出色，但对于更大或更复杂的形状，由于模式的数量会随组合爆炸式增长，该方法可能会显得过于沉重。然而，他们的工作强烈暗示，对于其他类似的形状（如长度为 10、14 等的循环），随机着色可能同样会成为冠军。

有趣的是，论文提到另一组研究人员也独立地使用类似的方法得出了相同的结论。但对于 Chen 和 Noel 来说，这段旅程的意义在于展示，即使是在一片红蓝交织的混沌之中，最“随机”的排列方式实际上是创造这些特定循环循环效率最高的。它提醒我们，有时，构建一个模式的最佳方式就是让骰子自由滚动。