Random independent sets in triangle-free and linear Berge-$C_4$-free hypergraphs

Source 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.