论文标题
独立的随机树和稀疏随机图
Independent Sets of Random Trees and of Sparse Random Graphs
论文作者
论文摘要
在有限的无向图$ g $中，一组独立的$ k $是该图的$ k $顶点，其中没有两个由边缘连接。令$ x_ {k}（g）$为图$ g $中$ k $的独立集数，让$α（g）= \ max \ {k \ geq0 \ geq0 \ colon x_ x_ {k}（g）\ neq0 \} $。 1987年，Alavi，Malde，Schwenk和Erdös问独立集序列$ x_ {0}（g），x_ {1}（g），\ ldots，x_ {α（g）}（g）}（g）（g）（g）$ a seee nimodal（序列是单个序列的上升和下降）。这个问题仍然开放。在2006年，Levit和Mandrescu表明，树的最后三分之一的独立设定序列正在减少。我们表明，随机树的独立集序列的前46.8％随着（指数）高概率而增加，因为顶点的数量转移到无穷大。因此，Alavi，Malde，Schwenk和Erdös的问题是``五分之四的true''，具有很高的可能性。 当单个顶点的预期程度很大时，我们还显示了Erdös-renyi随机图的独立集序列的单型（（指数）高概率，因为该图中的顶点数量是无限的，除了该模式附近的小区域外）。对于随机常规图显示了较弱的结果。 $ k $的独立集合的结构在$ k $方面有所不同，这是概率，统计物理，组合和计算机科学的概率。
An independent set of size $k$ in a finite undirected graph $G$ is a set of $k$ vertices of the graph, no two of which are connected by an edge. Let $x_{k}(G)$ be the number of independent sets of size $k$ in the graph $G$ and let $α(G)=\max\{k\geq0\colon x_{k}(G)\neq0\}$. In 1987, Alavi, Malde, Schwenk and Erdös asked if the independent set sequence $x_{0}(G),x_{1}(G),\ldots,x_{α(G)}(G)$ of a tree is unimodal (the sequence goes up and then down). This problem is still open. In 2006, Levit and Mandrescu showed that the last third of the independent set sequence of a tree is decreasing. We show that the first 46.8\% of the independent set sequence of a random tree is increasing with (exponentially) high probability as the number of vertices goes to infinity. So, the question of Alavi, Malde, Schwenk and Erdös is ``four-fifths true'', with high probability. We also show unimodality of the independent set sequence of Erdös-Renyi random graphs, when the expected degree of a single vertex is large (with (exponentially) high probability as the number of vertices in the graph goes to infinity, except for a small region near the mode). A weaker result is shown for random regular graphs. The structure of independent sets of size $k$ as $k$ varies is of interest in probability, statistical physics, combinatorics, and computer science.
