What random independent sets exist in triangle-free and linear Berge-C4-free hypergraphs?

Two hypergraph classes, two inclusion guarantees

The paper answers a distributional question rather than a size question. Instead of asking only how large an independent set must exist, it asks whether one random independent set can give every vertex a prescribed lower bound on its probability of being included. The answer depends on which local constraints the hypergraph satisfies.

In the triangle-free setting, the guarantee applies to every (r+1)-uniform hypergraph with no triangle, and the paper explicitly does not assume linearity. For a positive vertex-weight function w, the weighted degree of v is d_w(v) = Σ_{e ∋ v} (Π_{u ∈ e\{v}} w(u)/w(v))^(1/r). Theorem 1.1 gives a distribution on independent sets whose inclusion probability at v is at least (1 − e^(−a(v)))(1 + Λ_a(v)/log a(v)) for any activity vector a: V → (0,1), and Corollary 1.3 converts this into the stated bound P(v ∈ I) ≥ F_r(d_w(v)), where F_r(x) = (r/(r+1))·(r(r+1))^(−1/r)·(log x / x)^(1/r) up to an o_r(1) factor as x → +∞.

In the linear Berge-C4-free setting, Theorem 1.2 gives a different form. For every integer r ≥ 1 and every ε ∈ (0,1) there is δ = δ(r,ε) > 0 such that, for every total order on V and every activity vector a: V → (0,1), there is a distribution D on independent sets with P_{I∼D}(v ∈ I) ≥ (1 − ε)·min{a(v), δ·e^(−Γ_a(v))} simultaneously for all v. Corollary 1.4 turns this into a uniform statement: for every sufficiently large threshold D, one random independent set satisfies P(v ∈ I) ≥ (1 − ε)·(log d_w(v)/(r·d_w(v)))^(1/r) for every vertex with d_w(v) ≥ D.

The two guarantees are not the same statement at different scales. The triangle-free bound is vertex-by-vertex in terms of d_w(v) and carries a constant prefactor r/(r+1)·(r(r+1))^(−1/r). The Berge-C4-free bound is uniform above a threshold D and has leading constant 1, but it only applies to vertices whose weighted degree exceeds D, and it requires linearity plus the absence of Berge C4s.

Weighted degree is the right local parameter

The results are stated for a positive vertex-weight function w, not just for the unweighted degree d_G(v). The weighted degree d_w(v) = Σ_{e ∋ v} (Π_{u ∈ e\{v}} w(u)/w(v))^(1/r) reduces to d_G(v) when w ≡ 1, so the unweighted case is a special case rather than a separate theorem.

This matters because the inclusion guarantee is local. A vertex with large weighted degree is promised a larger inclusion probability, and the promise is made vertex by vertex rather than only on average over the vertex set. The paper's Corollary 1.3 is described as a hypergraph version of the local Shearer bound with a constant-factor loss, and Corollary 1.4 is the corresponding local statement for linear Berge-C4-free hypergraphs.

The weighted degree also controls the fractional chromatic number consequences. For a d-degenerate triangle-free (r+1)-uniform hypergraph, Corollary 1.5 gives χ_f(G) ≤ (r+1)/r · (r(r+1))^(1/r) · (d/log d)^(1/r) up to o_r(1). For a d-degenerate linear Berge-C4-free (r+1)-uniform hypergraph, Corollary 1.6 gives χ_f(G) ≤ (1 + o_r(1))·(r·d/log d)^(1/r). Here d is degeneracy, not maximum degree, and the conclusion is about fractional coloring, not ordinary coloring.

One ordered process produces both random sets

Both theorems are proved by analyzing the same ordered random pick process, extended from Martinsson and Steiner to hypergraphs. The vertices are processed in a fixed total order v_1 ≺ ⋯ ≺ v_n. At step i, the current vertex v_i is selected with probability q_i = p(a_{i−1}(v_i)), where p is a selection function and a_{i−1}(v_i) is the evolving mass of v_i.

If v_i is selected, it joins the independent set, and the mass of any future vertex affected by this choice is set to zero. If v_i is not selected, the affected future mass is divided by 1 − q_i instead. This compensation keeps the conditional expectation of each future mass unchanged, so E[a_i(v_j) | F_{i−1}] = a_{i−1}(v_j) and E[a_i(v_j)] = a(v_j). The process always outputs an independent set, because when the neck of an edge is processed, selecting it would have already zeroed the mass of the head, and p(0) = 0 prevents the head from being selected later.

The two theorems differ in the choice of p. Theorem 1.1 uses p(t) = 1 − e^(−t) together with a fixed-target modification. In the graph case one only needs to track the mass of an earlier neighbor of the target; in the hypergraph case one must also record whether the other earlier vertices of a backward edge have been selected, and this information is encoded in an auxiliary product. The good-order condition ensures that an outside step affects at most one factor of that product.

Theorem 1.2 uses the capped selection function p_ρ(t) = min{t, ρ} and a second-moment argument. The cap gives uniform control over the compensation factors on vertex weights while preserving the first moment of each vertex weight. To bound the second moment, the proof tracks products associated with backward edges and iterates one-step bounds over their subsets. Linearity and Berge-C4-freeness ensure that steps where several relevant factors can interact are sufficiently sparse, so the accumulated loss stays bounded.

Good order and Berge conditions control interference

The proofs rely on a structural condition on the vertex order. Given an order ≺, the head m(e) of an edge e is its largest vertex and the neck m*(e) is its second largest. The order is called good if, for any edge f and any vertex x not in f, the number of vertices v ∈ f with x ≺ v and E(x,v) ≠ ∅ is at most one, where E(x,v) = {e ∈ E : m*(e) = x, m(e) = v}. In a good order, a vertex outside a fixed edge can affect at most one later vertex of that edge. Every order of a triangle-free hypergraph is good, which is why Theorem 1.1 needs no linearity assumption.

The second setting replaces triangle-freeness with linearity plus the absence of Berge C4s. A hypergraph is linear if any two distinct edges intersect in at most one vertex, equivalently if it has no Berge cycle of length two. A Berge cycle of length ℓ consists of distinct edges e_1, …, e_ℓ and distinct core vertices x_1, …, x_ℓ with {x_i, x_{i+1}} ⊆ e_i, indices modulo ℓ. A Berge triangle is a Berge cycle of length three. The paper's second theorem allows Berge triangles, so it covers a class that the uncrowded setting excludes.

This distinction is the main scope difference between the two results. The triangle-free theorem is broader in one direction because it drops linearity, but its constant prefactor is larger. The Berge-C4-free theorem is narrower in its structural assumptions but achieves leading constant 1 in the fractional chromatic number bound, matching the coefficient in the maximum-degree list-coloring bound of Yu and Zhang and of Dhawan, Methuku, and Vo, while the parameter here is degeneracy and the conclusion is for fractional coloring.

Degeneracy bounds improve earlier coefficients

The fractional chromatic number consequences are stated for d-degenerate hypergraphs, meaning hypergraphs that admit a vertex order in which each vertex is the largest vertex of at most d edges. For triangle-free (r+1)-uniform hypergraphs, Corollary 1.5 gives χ_f(G) ≤ ((r+1)/r)·(r(r+1))^(1/r) + o_r(1))·(d/log d)^(1/r). For r = 1 this recovers the earlier graph bound of Martinsson and Steiner. For r ≥ 2 the paper states that it improves the leading coefficient in Dhawan's Theorem 1.4 by a factor of r^(1/r) and removes the linearity assumption.

For linear Berge-C4-free d-degenerate (r+1)-uniform hypergraphs, Corollary 1.6 gives χ_f(G) ≤ (1 + o_r(1))·(r·d/log d)^(1/r). For r = 1 this recovers the upper bound of Allen, Dhawan, and Noel. The paper also notes that the leading constant matches the maximum-degree list-coloring bound in Yu and Zhang and in Dhawan, Methuku, and Vo, but the parameter is degeneracy rather than maximum degree and the conclusion is fractional coloring rather than list coloring.

The paper's first result resolves Dhawan's Conjecture 5.4, which asked whether the same order of magnitude holds for triangle-free uniform hypergraphs without a linearity assumption. The second result attains the coefficient proposed in Dhawan's Conjecture 5.3 on the uncrowded class and extends the same bound to linear Berge-C4-free hypergraphs that may contain Berge triangles. A note in the paper records that version 4 of Dhawan's work announces forthcoming joint work proving the conjectured leading-coefficient degeneracy bound with a local-demand version for uncrowded hypergraphs; the paper states that at the time of writing the cited version contains only this announcement, and that its own second theorem has a different scope because it allows Berge triangles.

Thresholds and structural assumptions bound the claims

The triangle-free inclusion bound is asymptotic in the weighted degree: it is stated as d_w(v) → +∞, with an o_r(1) term that depends on r. It is not a finite-degree guarantee, and the constant prefactor r/(r+1)·(r(r+1))^(−1/r) is not 1. The bound holds for every vertex individually, but the asymptotic regime is part of the statement.

The Berge-C4-free inclusion bound is uniform only above a threshold. For every sufficiently large D there is one random independent set that works simultaneously for all vertices with d_w(v) ≥ D, with P(v ∈ I) ≥ (1 − o_r(1))·(log d_w(v)/(r·d_w(v)))^(1/r) as D → +∞. Vertices below D are not covered by this uniform statement. The proof of Corollary 1.4 sets the activity to 1/2 below the cutoff to keep a ∈ (0,1)^V and imposes no marginal requirement at those vertices.

The structural assumptions are also part of the scope. The first theorem requires a good order, which every triangle-free hypergraph admits, so it applies to all triangle-free (r+1)-uniform hypergraphs without linearity. The second theorem requires linearity and the absence of Berge C4s, but permits Berge triangles. Neither theorem is stated for arbitrary hypergraphs, and the fractional chromatic number corollaries inherit the corresponding degeneracy and structural conditions.

Compare prefactor, threshold, and structural cost

The most useful comparison in this paper is not which bound is larger in the abstract, but which combination of prefactor, threshold, and structural assumption a reader needs. The triangle-free result pays a constant prefactor r/(r+1)·(r(r+1))^(−1/r) and an o_r(1) term, but it requires no linearity and gives a vertex-by-vertex bound in terms of d_w(v). The Berge-C4-free result achieves leading constant 1 and a uniform guarantee above a threshold D, but it requires linearity and the absence of Berge C4s, and it leaves vertices below D outside the uniform statement.

For the fractional chromatic number, the same trade-off appears in the coefficients. Corollary 1.5 carries the factor (r+1)/r·(r(r+1))^(1/r) for d-degenerate triangle-free hypergraphs, while Corollary 1.6 carries leading constant 1 for d-degenerate linear Berge-C4-free hypergraphs. The paper states that for r ≥ 2 the triangle-free bound improves Dhawan's coefficient by r^(1/r) and drops linearity, and that the Berge-C4-free bound matches the maximum-degree list-coloring coefficient while using degeneracy and fractional coloring.

The practical reading is therefore conditional on the hypergraph at hand. If the hypergraph is triangle-free but not known to be linear, the first result is the applicable one, with its prefactor and its d_w(v) → +∞ asymptotics. If the hypergraph is linear and Berge-C4-free but may contain Berge triangles, the second result gives the sharper leading constant, provided the vertex of interest has weighted degree at least the threshold D. The paper's own framing places the second theorem's scope as different from the announced uncrowded-hypergraph work, precisely because it allows Berge triangles.

Sources used in this answer