论文标题
关于随机图中交替路径的数量
On the number of alternating paths in random graphs
论文作者
论文摘要
在编码理论的嘈杂通道模型中，我们希望通过优化代码的各种参数来检测传输过程中引入的错误。 Bennett，Dudek和Laforge用在2016年边缘颜色完整的两部分图的交替路径的语言中构造了此问题的变体。在这里，我们将此问题扩展到随机图$ \ Mathbb {g}（n，p）$。我们寻求交替的连接性，$κ_{r，\ ell}（g）$，这是最大$ t $，使得$ g $ $ g $的$ r $ - edged颜色是由$ t $内部偏见和交替的$ t $连接的（即，同一彩色的连续路径）的长度$ $ $ $ \ ell $ \ el el $ \ el e el n noctanible and t $ t $连接。我们有三个主要的结果，即此参数在$ \ mathbb {g}（n，p）$中的行为方式基本上涵盖了$ p $的所有范围：一个用于长度二的路径，一个用于密集的情况，一个用于稀疏的情况。对于长度二的路径，我们发现$κ_{r，\ ell}（g）$本质上是一对顶点的代码。对于$ p $恒定的密集情况，我们能够达到最小程度的自然上限（减去某些相交）或一对顶点之间的分离路径总数。对于稀疏的情况，我们能够找到达到最小程度的自然障碍物的着色，或者（稍微精确的结果略低）图中一定长度的总路径总数。我们将这个稀疏的情况分解为$ p $的范围，对应于$ \ mathbb {g}（n，p）$具有直径$ k $或$ k+1 $。我们对相似的参数和对伪图形的概括进行了一些评论。
In the noisy channel model from coding theory, we wish to detect errors introduced during transmission by optimizing various parameters of the code. Bennett, Dudek, and LaForge framed a variation of this problem in the language of alternating paths in edge-colored complete bipartite graphs in 2016. Here, we extend this problem to the random graph $\mathbb{G}(n,p)$. We seek the alternating connectivity, $κ_{r,\ell}(G)$, which is the maximum $t$ such that there is an $r$-edge-coloring of $G$ such that any pair of vertices is connected by $t$ internally disjoint and alternating (i.e. no consecutive edges of the same color) paths of length $\ell$. We have three main results about how this parameter behaves in $\mathbb{G}(n,p)$ that basically cover all ranges of $p$: one for paths of length two, one for the dense case, and one for the sparse case. For paths of length two, we found that $κ_{r,\ell}(G)$ is essentially the codegree of a pair of vertices. For the dense case when $p$ is constant, we were able to achieve the natural upper bounds of minimum degree (minus some intersection) or the total number of disjoint paths between a pair of vertices. For the sparse case, we were able to find colorings that achieved the natural obstructions of minimum degree or (in a slightly less precise result) the total number of paths of a certain length in a graph. We broke up this sparse case into ranges of $p$ corresponding to when $\mathbb{G}(n,p)$ has diameter $k$ or $k+1$. We close with some remarks about a similar parameter and a generalization to pseudorandom graphs.
