Generating random graphs in biased Maker‐Breaker games
Generating random graphs in biased Maker‐Breaker games
复制标题
在有偏差的 Maker-Breaker 游戏中生成随机图
DOI：
10.1002/rsa.20619
复制
发表时间：
2013
影响因子：
1
通讯作者：
Humberto Naves
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Michael Krivelevich;Humberto Naves
我们给出了一个连接有偏Maker-Breaker对策和随机图的局部弹性问题的一般方法。我们利用这种方法证明了新的结果，并得到了一些关于有偏的Maker-Breaker对策的已知结果。特别地，我们证明了当b=o(N)时，Maker在E(Kn)上玩一个(1：B)对策时可以建立一个泛圈图(即包含所有可能长的圈的图)。作为另一个应用，我们证明了对于b=Θ(n/lnn)，在E(Kn)上玩一个(1：B)对策，Maker可以建立一个图，它包含所有具有线性长度的光路的最大度Δ=O(1)的生成树的副本(树T中的光路是指所有内部顶点恰好在T中的2度的路)。©2015威利期刊公司随机结构。2015年，47,615-634
We present a general approach connecting biased Maker‐Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker‐Breaker games. In particular, we show that for b=o(n) , Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a (1:b) game on E(Kn) . As another application, we show that for b=Θ(n/lnn) , playing a (1:b) game on E(Kn) , Maker can build a graph which contains copies of all spanning trees having maximum degree Δ=O(1) with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 615–634, 2015
在 Maker-Breaker 游戏中快速构建生成树
DOI：
10.1137/140976054
发表时间：
2015
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Dennis Clemens;Asaf Ferber;Roman Glebov;Dan Hefetz;Anita Liebenau
通讯作者：
Anita Liebenau
对抗性边缘去除后几乎跨越随机图的子图
DOI：
10.1017/s0963548313000199
发表时间：
2013
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz
通讯作者：
A. Taraz