Saturation in random hypergraphs

doi:10.1017/S0963548325100229

Saturation in random hypergraphs

2025-10-01

0

PRE

AI

DOI：10.1017/S0963548325100229

原文链接

原文求助

摘要

En 中文

设 $K<^>r_n$ 是一个完全的 $r$-均匀超图，其顶点集为 $[n] \, :\! = \{1,2,\ldots ,n\}$，边集为 $\binom {[n]}{r}$。我们通过以概率 $p$ 独立保留 $K<^>r_n$ 的每条边来构造 $G<^>r(n,p)$。一个 $r$-均匀超图 $H\subseteq G$ 是 $F$-饱和的，如果 $H$ 不包含 $F$ 的任何副本，但 $H$ 在 $G$ 中缺失的任何边都会产生 $F$ 的一个副本。此外，我们称 $H$ 在 $G$ 中是弱 $F$-饱和的，如果 $H$ 不包含 $F$ 的任何副本，但 $H$ 在 $G$ 中缺失的边可以按某种顺序逐条加回，使得每条边都产生一个新的 $F$ 副本。$G$ 中 $F$-饱和超图的最小边数记为 ${\textit {sat}}(G,F)$，弱 $F$-饱和超图的最小边数记为 $\mathop {\mbox{$w$-${sat}$}}\! (G,F)$。2017年，Kor & aacute;ndi 和 Sudakov 开创了对随机图中饱和问题的研究，他们证明了对于常数 $p$，以高概率 ${\textit {sat}}(G(n,p),K_s)=(1+o(1))n\log _{\frac {1}{1-p}}n$，且 $\mathop {\mbox{$w$-${sat}$}}\! (G(n,p),K_s)=\mathop {\mbox{$w$-${sat}$}}\! (K_n,K_s)$。推广他们的结果，本文中，我们解决了随机超图 $G<^>r(n,p)$ 中关于 $K_s<^>r$ 完全子图的饱和问题，对于所有 $2\le r \lt s$ 和常数 $p$。

Keyword:

Saturation

weak saturation

random hypegraphs

Saturation in random hypergraphs

摘要

期刊

机构