Random independent sets in triangle-free and linear Berge-C4-free hypergraphs
Abstract
We study probability distributions on independent sets of uniform hypergraphs with local constraints. For a positive vertex-weight function w on an (r+1)-uniform hypergraph, define the weighted degree of vertex v by dw(v):= ∑e∋ v ( ∏u∈ e∖{v}w(u)/w(v) )1/r. For each fixed r≥1, our first result gives, in every triangle-free (r+1)-uniform hypergraph (without a linearity assumption), a random independent set I satisfying ℙ(v∈ I)≥ ( r/(r+1)(r(r+1))−1/r+or(1) ) ((log dw(v))/dw(v))1/r, dw(v)→+∞. The same result also implies that every d-degenerate triangle-free (r+1)-uniform hypergraph satisfies χf(G)≤ ( (r+1)/r(r(r+1))1/r+or(1) ) (d/(log d))1/r, d→+∞. Our second result concerns linear Berge-C4-free hypergraphs which allow Berge triangles. In this setting, for every sufficiently large threshold D, there exists a random independent set I such that, uniformly over all vertices with dw(v)≥ D, ℙ(v∈ I)≥ (1−or(1)) ((log dw(v))/(r dw(v)))1/r, D→+∞. It also yields χf(G)≤ (1+or(1)) (rd/(log d))1/r for d-degenerate linear Berge-C4-free (r+1)-uniform hypergraphs. Both results are based on the ordered random pick process originated from Martinsson and Steiner. By choosing different selection functions and iteration, we prove the output of the random process gives the required random independent set.
Related
- Rainbow Berge Hamiltonicity in edge-colored random k-uniform hypergraphs
- Variance of random greedy independent sets in triangle-free graphs
- Random independent sets in uncrowded hypergraphs
- Spectral extremal hypergraphs without long Berge cycles
- A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs
BibTeX
@misc{yu2026random,
title = {{Random independent sets in triangle-free and linear Berge-$C_4$-free hypergraphs}},
author = {Jing Yu and Junchi Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06499},
eprint = {2610.06499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06499},
}
RIS
TY - UNPB
TI - Random independent sets in triangle-free and linear Berge-C_4-free hypergraphs
AU - Jing Yu
AU - Junchi Zhang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06499
UR - https://arxiv.org/abs/2610.06499
AB - We study probability distributions on independent sets of uniform hypergraphs with local constraints. For a positive vertex-weight function w on an (r+1)-uniform hypergraph, define the weighted degree of vertex v by d_w(v):= ∑_e∋ v ( ∏_u∈ e∖{v}w(u)/w(v) )^1/r. For each fixed r≥1, our first result gives, in every triangle-free (r+1)-uniform hypergraph (without a linearity assumption), a random independent set I satisfying ℙ(v∈ I)≥ ( r/(r+1)(r(r+1))^−1/r+o_r(1) ) ((log d_w(v))/d_w(v))^1/r, d_w(v)→+∞. The same result also implies that every d-degenerate triangle-free (r+1)-uniform hypergraph satisfies χ_f(G)≤ ( (r+1)/r(r(r+1))^1/r+o_r(1) ) (d/(log d))^1/r, d→+∞. Our second result concerns linear Berge-C_4-free hypergraphs which allow Berge triangles. In this setting, for every sufficiently large threshold D, there exists a random independent set I such that, uniformly over all vertices with d_w(v)≥ D, ℙ(v∈ I)≥ (1−o_r(1)) ((log d_w(v))/(r d_w(v)))^1/r, D→+∞. It also yields χ_f(G)≤ (1+o_r(1)) (rd/(log d))^1/r for d-degenerate linear Berge-C_4-free (r+1)-uniform hypergraphs. Both results are based on the ordered random pick process originated from Martinsson and Steiner. By choosing different selection functions and iteration, we prove the output of the random process gives the required random independent set.
ER -