OpenAlex ·
Random independent sets in triangle-free and linear Berge-$C_4$-free hypergraphs
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.06499
- Original
- Read it at the publisher
- Topics
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 \[ d_w(v):= \sum_{e\ni v} \left( \prod_{u\in e\setminus\{v\}}\dfrac{w(u)}{w(v)} \right)^{1/r}. \] For each fixed $r\geq1$, our first result gives, in every triangle-free $(r+1)$-uniform hypergraph (without a linearity assumption), a random independent set $I$ satisfying \[ \mathbb P(v\in I)\geq \left( \frac{r}{r+1}(r(r+1))^{-1/r}+o_r(1) \right) \left(\frac{\log d_w(v)}{d_w(v)}\right)^{1/r}, \qquad d_w(v)\to+\infty. \] The same result also implies that every $d$-degenerate triangle-free $(r+1)$-uniform hypergraph satisfies \[ χ_f(G)\leq \left( \dfrac{r+1}{r}(r(r+1))^{1/r}+o_r(1) \right) \left(\dfrac{d}{\log d}\right)^{1/r}, \qquad d\to+\infty. \] 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)\geq D$, \[ \mathbb P(v\in I)\geq (1-o_r(1)) \left(\frac{\log d_w(v)}{r\,d_w(v)}\right)^{1/r}, \qquad D\to+\infty. \] It also yields \[ χ_f(G)\leq (1+o_r(1)) \left(\frac{rd}{\log d}\right)^{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.