.png){kind=icon}
返回
Creating Subgraphs in Semi-Random Hypergraph Games
.png){kind=icon}
PRE
AI
DOI：10.37236/13447.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
半随机超图过程是半随机图过程的一个自然推广，可以看作是一个单人游戏。对于固定的 r < s，从一个包含 n 个顶点的空超图开始，每一轮中，一个由 r 个顶点组成的集合 U 会独立且均匀随机地呈现给玩家。然后玩家选择一个由 s-r 个顶点组成的集合 V，并将超边 U boolean OR V 添加到超图中。对于一个固定的（单调）增图性质，玩家的目标是在尽可能少的轮数内以高概率强制该图满足此性质。我们重点关注玩家目标为构造一个与任意固定超图 H 同构的子图的情况。在 r = 1 的情况下，所需轮数的阈值已根据 H 的退化度得知。在 2 ≤ r < s 的情况下，我们给出了该阈值的一般 H 的上下界，并针对特定情况下的完全图找到了进一步改进的上界。我们确定了上下界匹配的情况。我们还通过找到各种路径和循环的确切阈值，证明了下界并非总是紧的。
Keyword:
semi-random hypergraph process
subgraph creation
monotone increasing property
degeneracy
threshold analysis
期刊
E
IF:
0.7
论文数:
183
被引数:
0
机构
查看更多机构
引用论文
暂无论文信息