论文标题
强大的完整未成年人
Strong complete minors in digraphs
论文作者
论文摘要
Kostochka和Thomason独立地表明，任何平均度$ω（r \ sqrt {\ log r}）$的图都包含$ k_r $ binor。特别是，任何具有色数$ω（r \ sqrt {\ log r}）$的图形都包含一个$ k_r $ minor，这是哈德威格（Hadwiger）著名猜想的部分结果。在本文中，我们在定向环境中调查了这些结果的类似物。有几种方法可以在挖掘中定义未成年人。一种自然的方式是如下。一个强的$ \ oferrightRarow {k} _r $ binor是一个挖掘图，其顶点集被分配到$ r $零件中，以使每个部分都诱导一个强烈连接的子数字，并且在任何两个不同零件之间的每个方向上至少都有一个边缘。我们调查了二分法数和最小距离的界限，该图形迫使存在强的$ \ oferrightArrow {k} _r $ suinors作为子数字。特别是，我们表明，任何具有二十语号码的比赛至少$ 2R $都包含一个强的$ \ oferrightArrow {k} _r $ minor，以及任何具有最低超级$ω（r \ sqrt {\ log log r}）$的比赛都包含一个强大的$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ \ frine。后者的结果紧密到隐含常数，并且可以被视为与Kostochka和Thomason经典结果的强硬类似物。最后，我们表明没有函数$ f：\ mathbb {n} \ rightArrow \ mathbb {n} $，因此任何具有最小超高级的挖掘物至少$ f（r）$都包含一个强$ \ overrightArrow {k} _r $ bintor，但是当考虑dichromantic nork dichrolotic编号时，但是这些功能存在。
Kostochka and Thomason independently showed that any graph with average degree $Ω(r\sqrt{\log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $Ω(r\sqrt{\log r})$ contains a $K_r$ minor, a partial result towards Hadwiger's famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong $\overrightarrow{K}_r$ minor is a digraph whose vertex set is partitioned into $r$ parts such that each part induces a strongly-connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong $\overrightarrow{K}_r$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least $2r$ contains a strong $\overrightarrow{K}_r$ minor, and any tournament with minimum out-degree $Ω(r\sqrt{\log r})$ also contains a strong $\overrightarrow{K}_r$ minor. The latter result is tight up to the implied constant, and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function $f: \mathbb{N} \rightarrow \mathbb{N}$ such that any digraph with minimum out-degree at least $f(r)$ contains a strong $\overrightarrow{K}_r$ minor, but such a function exists when considering dichromatic number.
