Edge densities of drawings of graphs with one forbidden cell

本文系统研究了禁止特定单元类型的图绘制（$\mathfrak{c}$-free drawings）的边密度问题，针对不同的绘图风格、图类型及单元类型给出了紧致的上下界，证明了除一种特殊情况外边密度均为线性或超线性，并完整刻画了不含特定无交叉单元类型的简单图类，同时改进了拟平面绘制的边密度下界。

要点

这篇论文就像是在研究**“如何在一张纸上画出一张复杂的地图，同时严格遵守某些‘禁飞区’规则”**。

想象一下，你是一位城市规划师（或者是一个画图的艺术家），你的任务是在平面上画出许多城市（顶点）和连接它们的道路（边）。当你画完这些道路后，它们会把整张纸分割成许多个**“区域”**（就像地图上的街区或岛屿）。

这篇论文的核心问题就是：如果我们规定某些特定形状的“区域”绝对不能出现，那么这张地图上最多能画多少条路？

1. 核心概念：什么是“单元格类型”？

在画图中，道路和交叉点把纸分成了很多块。每一块区域都有一个“身份证”，叫做单元格类型（Cell Type）。

• 这个身份证记录了：这块区域的边界是由几个城市、几条路段和几个十字路口组成的。
• 比如，一个“三角形区域”可能由 3 个路口和 0 个城市组成；另一个“三角形区域”可能由 3 个城市和 0 个路口组成。虽然它们看起来都是三角形，但在数学上，它们的“身份证”是不同的。

论文的任务就是： 如果我们禁止出现某种特定身份证的区域（比如“禁止出现由 3 个路口组成的三角形区域”），我们的地图还能画得有多密？

2. 主要发现：路能修多密？

作者们发现，根据你禁止的区域类型不同，地图的“拥挤程度”（边密度）会有天壤之别：

• 情况 A：禁止的是“大怪物”区域
  如果你禁止的区域形状很复杂（比如需要很多个路口或城市才能拼出来），那么恭喜你！你可以把路修得非常密，几乎每两个城市之间都能修路。这种情况下，路的数量是平方级增长的（$n^2$），就像在一个拥挤的市中心，大家几乎都能互相连通。

• 情况 B：禁止的是“小精灵”区域
  如果你禁止的是那些很小、很简单的区域（比如由 3 个路口组成的三角形，或者由 4 个路口组成的四边形），那么情况就变了。

  • 线性增长： 大多数情况下，路的数量只能随着城市数量线性增长（$n$）。这意味着你不能让地图太拥挤，城市多了，路就必须稀疏一些，否则就会不小心造出那个被禁止的“小精灵”区域。
  • 超线性增长（特例）： 有一个非常特殊的“小精灵”（由 4 个路口组成的区域，且没有城市），作者们发现它很棘手。他们证明了在这种限制下，路可以比线性多，但具体能多到什么程度（是像 $n^{1.5}$ 还是 $n^2$），目前还是个未解之谜。

3. 具体的“战绩”与改进

作者们不仅给出了理论上限（最多能修多少路），还动手造出了具体的地图（构造），证明了这些路确实能修出来。

• 打破旧纪录： 以前大家认为，在一种叫做“准平面图”（Quasiplanar，即没有三条路互相交叉）的画法中，路的上限大概是 $8n$。作者们通过一种巧妙的“同心圆 + 锯齿”画法，把能修的路从$7n$提升到了 **$7.5n$**。这就像是在同样的城市面积下，通过优化交通设计，多修了 50% 的路！
• 发现新大陆： 他们发现，有些图虽然不能画成“准平面图”，但却可以画成“没有特定小三角形”的图。这说明这两个概念虽然很像，但其实是不一样的。

4. 一个有趣的“万能画法”

论文还解决了一个大问题：是不是所有的图，只要禁止某些特定的“简单区域”，都能画出来？

作者们发现了一个神奇的规律：

• 如果你禁止的区域边界上没有十字路口（也就是说，这个区域只是由几条没交叉的路围成的），那么除了极少数非常特殊的图（比如只有 3 个点的三角形，或者像星星一样的图）之外，几乎所有图都能画出来！
• 这就好比说，只要你不禁止“没有交叉口的简单街区”，那么无论你的城市网络多复杂，你总能找到一种画法把它画在纸上，而不违反规则。

5. 总结与未解之谜

这篇论文就像是在绘制一张“地图拥挤度指南”：

1. 大部分规则下，地图要么可以非常拥挤（平方级），要么必须保持稀疏（线性）。
2. 作者们填补了很多空白，给出了更精确的“拥挤度”数字。
3. 最大的悬念：关于那个由 4 个路口组成的特殊区域，我们目前知道路可以修得比线性多，但不知道能不能修到平方级。作者们猜测可以，但还需要有人去证明。

一句话总结：
这就好比在研究“如果禁止在房间里放某种形状的家具，这个房间最多能塞进多少件家具？”作者们发现，大多数时候，房间要么能塞满，要么只能塞一点点；而对于一种特殊的家具，他们虽然知道能塞不少，但到底能不能塞满，还在等待下一个天才来揭晓答案。

技术摘要

这是一份关于论文《Edge densities of drawings of graphs with one forbidden cell》（禁止一种特定单元类型的图绘制的边密度）的详细技术总结。

1. 研究背景与问题定义

核心问题：
图论中有一类重要的图类，定义为允许某种特定绘制方式（drawing）的图。传统的“平面图”禁止边交叉，“准平面图”（quasiplanar）禁止三条边两两交叉。本文引入了一个更精细的视角：禁止特定类型的“单元”（cell）。

• 定义： 一个连通拓扑绘制将平面划分为若干个区域，称为“单元”（cells）。
• 单元类型（Cell Type）： 由单元边界上的顶点（vertices）、边段（edge segments）和交叉点（crossings）的循环序列定义。例如，一个 $\mathcal{C}_3$ 单元（文中记为 $\mathcal{C}_3$ 或 $\mathcal{C}_3$-cell）是指边界上有 3 个交叉点、3 个边段且没有顶点的单元。
• 研究目标： 给定一个固定的单元类型 $c$，研究所有$c$-free（即不包含任何类型为 $c$ 的单元）绘制的图的边密度（edge density），即 $n$ 个顶点的图最多能有多少条边。
• 绘制类型： 研究涵盖了三种绘制风格：
  1. 任意绘制（Arbitrary drawings）： 允许边多次交叉，允许平行边（多重图）。
  2. 非同伦绘制（Non-homotopic drawings）： 不允许存在“空透镜”（empty lens，即由两条边围成且内部无顶点或交叉点的区域）。
  3. 简单绘制（Simple drawings）： 任意两条边最多相交一次（无平行边，无自交）。

2. 方法论

本文结合了构造性下界（Lower Bounds）和基于放电法（Discharging Arguments）的上界（Upper Bounds）证明。

• 下界构造（Constructions）：
  • 作者设计了多种新颖的图绘制构造，以展示在禁止特定单元类型时，图仍然可以拥有大量的边。
  • 对于完全图 $K_n$，作者证明了除了少数几种特定单元类型外，$K_n$ 都存在简单绘制。
  • 针对 $\mathcal{C}_4$-free 和 $\mathcal{C}_3$-free 等特定情况，作者利用网格、环面（torus）和多重图构造，实现了线性甚至二次方的边密度。
• 上界证明（Upper Bounds）：
  • 主要使用了放电法（Discharging method）。这是一种组合数学中常用的技术，通过给图的元素（如顶点、边、单元）分配“电荷”，然后根据局部规则重新分配，证明总电荷量与边数之间的关系。
  • 利用欧拉公式的变体（Lemma 2）和关于小单元数量的引理（Lemma 3），建立了单元大小、数量与边数之间的不等式关系。
  • 特别是对于 $\mathcal{C}_5$-free 和 $\mathcal{C}_3$-free 的情况，通过精细计算每个单元对总边数的贡献，导出了线性上界。

3. 主要贡献与结果

A. 边密度的分类（线性 vs 超线性）

对于绝大多数单元类型 $c$，作者确定了 $c$-free 绘制的边密度是线性（$O(n)$）还是超线性（$\Omega(n^{1+\epsilon})$ 或 $O(n^2)$）。

• 线性上界的情况：
  • $\mathcal{C}_3$-free（禁止 3 交叉单元）： 在非同伦多重图绘制中，边数上限为 $8n - 20$（紧确界）。在简单图绘制中，上限为$7n - 20$。
  • $\mathcal{C}_5$-free（禁止 5 交叉单元）： 在同伦限制下，边数上限为 $6n - 12$。
  • $\mathcal{C}_4$-free（禁止 4 交叉单元）： 这是一个特例。对于多重图，下界为 $9n-18$，但上界未知（可能是无穷大或超线性）。对于简单图，下界为$6n-12$。
• 超线性/二次方密度的情况：
  • $\mathcal{C}_4$-free（简单绘制）： 在平面上，作者构造了 $\Omega(n^{3/2})$ 的边密度（Construction 10）。在环面上，作者构造了 $\Omega(n^2)$ 的边密度（Construction 9）。
  • $\mathcal{C}_4$-free（非同伦绘制）： 作者构造了 $\Omega(n^2)$ 的边密度（Construction 11），表明在放松“简单”限制后，边密度可以是二次方的。
  • 大尺寸单元： 对于大小 $\ge 6$ 的单元类型，完全图 $K_n$ 通常存在简单绘制，因此边密度为 $\Theta(n^2)$。

B. 具体改进与突破

1. 准平面图（Quasiplanar Graphs）的改进：
   • 准平面图等价于禁止 $\mathcal{C}_3$ 单元（在简单图中）。
   • 作者将非同伦简单准平面图的下界从 $7n - 28$提升至 **$7.5n - 28$**（Construction 6）。
   • 对于 $\mathcal{C}_3$-free 简单图，下界提升至 **$8n - 28$**（Construction 7），几乎达到了$8n-20$ 的上界。
2. $\mathcal{C}_3$-free 与准平面图的区别：
   • 证明了存在简单图可以绘制为 $\mathcal{C}_3$-free，但不能绘制为非同伦准平面图（Proposition 5）。这打破了之前认为两者在非同伦多重图情形下等价的直觉，表明在简单图情形下这两个类是不同的。
3. 完全图的绘制能力：
   • 证明了对于几乎所有单元类型 $c$，完全图 $K_n$ 都存在简单 $c$-free 绘制。
   • 对于任意单元类型 $c$，$K_n$ 都存在（非简单）$c$-free 绘制（Construction 3）。

C. 结构刻画（Structure Characterization）

• 无交叉边界的单元： 对于边界不包含任何交叉点的单元类型 $c$（即由 $m$ 个顶点和 $m$ 条未交叉边围成的单元），作者给出了一个完整的刻画：
  • 除了 $K_3$（当 $c$ 为三角形单元）和星图 $K_{1, m/2}$（当 $c$ 为偶数边形单元）外，所有连通简单图都 admit 一个简单 $c$-free 绘制。
  • 这意味着，只要禁止的单元不涉及交叉点，绝大多数图都能避免这种单元。

4. 关键数据总结（基于表 1 和表 2）

禁止单元类型	图类型	绘制类型	下界 (Lower Bound)	上界 (Upper Bound)	备注
$\mathcal{C}_3$	多重图	非同伦	$8n-20$|$8n-20$	紧确
$\mathcal{C}_3$	简单图	非同伦	**$8n-28$** (新) |$8n-20$	差距缩小
$\mathcal{C}_3$	简单图	简单	$7n-30$(新) |$7n-20$	紧确
$\mathcal{C}_4$	多重图	非同伦	$9n-18$|$\infty$ (未知)	开放问题
$\mathcal{C}_4$	简单图	简单	$\Omega(n^{3/2})$	$\binom{n}{2}$	开放问题
$\mathcal{C}_4$	简单图	环面	$\Omega(n^2)$	$\binom{n}{2}$	二次方
$\mathcal{C}_5$	多重图	非同伦	$6n-12$|$6n-12$	紧确
其他 (大小 $\ge 6$)	简单图	简单	$\binom{n}{2}$	$\binom{n}{2}$	完全图可绘制

5. 意义与未来展望

• 理论意义： 本文首次系统性地研究了“禁止单一单元类型”这一图绘制问题，填补了从禁止边交叉（平面图）到禁止特定局部拓扑结构之间的空白。它揭示了图的边密度不仅取决于交叉的数量，还取决于交叉形成的局部几何结构（单元类型）。
• 方法创新： 成功将放电法应用于单元类型的计数，并设计了复杂的拓扑构造（如环面绘制、多重图交错）来突破线性界限。
• 开放问题（Open Problems）：
  1. $\mathcal{C}_4$-free 简单绘制的密度： 在平面上，简单 $\mathcal{C}_4$-free 绘制的边密度是线性的还是二次方的？作者猜想是二次方（Conjecture 8），但目前下界仅为 $\Omega(n^{3/2})$。
  2. 通用性： 哪些单元类型 $c$ 使得所有连通图都存在 $c$-free 绘制？目前仅对无交叉边界的单元类型给出了完整答案。
  3. 准平面图的上界： 简单准平面图的上界 $8n-20$是否紧确？即是否存在$8n-O(1)$ 的构造？

总结： 这篇论文极大地扩展了我们对图绘制中局部拓扑约束与全局边密度之间关系的理解，提供了紧确的界限，并提出了关于 $\mathcal{C}_4$-free 图密度的重要猜想，为未来的极值图论研究指明了方向。