论文标题
猜测数字和极端图理论
Guessing Numbers and Extremal Graph Theory
论文作者
论文摘要
对于给定数量的颜色，$ s $，图的猜测数字是图表的最大颜色家族的（基本$ s $）对数（基本$ s $）对数，以便可以从附近的顶点的颜色确定每个顶点的颜色。该数量与网络编码，电路复杂性和图形熵的问题有关。我们在经典的极端问题的背景下研究了图形的猜测数量，及其与禁忌子图属性的关系。我们发现有关猜测数字$ \ leq a $的属性的极端数字，对于固定$ a $。此外，我们在此特性的饱和数上找到了上限，以及一种构造这两个极端之间的进一步饱和图的方法。我们表明，对于固定数量的颜色，猜测数字等同于禁止有限的子图集。
For a given number of colors, $s$, the guessing number of a graph is the (base $s$) logarithm of the cardinality of the largest family of colorings of the vertex set of the graph such that the color of each vertex can be determined from the colors of the vertices in its neighborhood. This quantity is related to problems in network coding, circuit complexity and graph entropy. We study the guessing number of graphs as a graph property in the context of classic extremal questions, and its relationship to the forbidden subgraph property. We find the extremal number with respect to the property of having guessing number $\leq a$, for fixed $a$. Furthermore, we find an upper bound on the saturation number for this property, and a method to construct further saturated graphs that lie between these two extremes. We show that, for a fixed number of colors, bounding the guessing number is equivalent to forbidding a finite set of subgraphs.
