PaperlayerView exact revision on arXiv

Source-linked AI summary

The number of independent sets in an irregular graph

Ashwin Sah, Mehtaab Sawhney, David Stoner, Yufei Zhao

arXiv:1805.04021v3math.CO

TL;DR

The paper addresses extending the regular-graph extremal independent-set bound to irregular graphs, including the conjecture that complete bipartite components are extremal. The proofs use an induction strategy and establish analytic inequalities that remove the maximum-degree restriction of earlier computer-assisted work. The irregular upper bound is sharp for disjoint unions of complete bipartite graphs, and the lower bound is sharp for disjoint unions of cliques.

  • Problem

    The paper addresses extending the regular-graph extremal independent-set bound to irregular graphs, including the conjecture that complete bipartite components are extremal.

    Source: §1 · pp. 1–2

  • Method

    The proofs use an induction strategy and establish analytic inequalities that remove the maximum-degree restriction of earlier computer-assisted work.

    Source: §1 · p. 4

  • Results

    The irregular upper bound is sharp for disjoint unions of complete bipartite graphs, and the lower bound is sharp for disjoint unions of cliques.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    For graphs with λ > 0, Theorem 1.7 gives a degree-dependent expression involving ((d_v + 1)λ + 1)^{1/(d_v+1)}.

    Source: §1 · p. 3

    Expressions for extrema under minimum-, average-, or maximum-degree constraints are not included because they are somewhat complicated.

    Source: §5.1 · p. 11

Abstract

from arXiv · show

Settling Kahn's conjecture (2001), we prove the following upper bound on the number $i(G)$ of independent sets in a graph $G$ without isolated vertices: \[ i(G) \le \prod_{uv \in E(G)} i(K_{d_u,d_v})^{1/(d_u d_v)}, \] where $d_u$ is the degree of vertex $u$ in $G$. Equality occurs when $G$ is a disjoint union of complete bipartite graphs. The inequality was previously proved for regular graphs by Kahn and Zhao. We also prove an analogous tight lower bound: \[ i(G) \ge \prod_{v \in V(G)} i(K_{d_v+1})^{1/(d_v + 1)}, \] where equality occurs for $G$ a disjoint union of cliques. More generally, we prove bounds on the weighted versions of these quantities, i.e., the independent set polynomial, or equivalently the partition function of the hard-core model with a given fugacity on a graph.

1. Introduction

The introduction extends extremal bounds for independent sets from regular to irregular graphs, proving Kahn’s conjectured upper bound and an analogous lower bound. It also establishes weighted versions for the independent set polynomial, with equality characterized by unions of complete bipartite graphs or cliques.

1. Introduction

  • The regular-graph upper-bound problem asks which d-regular graph on n vertices maximizes the number of independent sets; Kahn and Zhao proved the complete-bipartite extremal case.Kahn proved the bipartite case using entropy, and Zhao extended it to all regular graphs.Source: §1 · p. 1
  • Independent-set counting is motivated in part by combinatorial problems that can be phrased in terms of independent sets in graphs and hypergraphs.The introduction connects this area to work on the hypergraph container method.Source: §1 · p. 1
  • For graphs without isolated vertices, the paper proves Kahn’s conjectured irregular-graph upper bound, with equality exactly for disjoint unions of complete bipartite graphs.The conjecture specifies these extremizers for graphs with a prescribed degree-degree distribution.Source: §1 · p. 2
  • The irregular-graph lower bound has equality exactly for disjoint unions of cliques.This extends the regular-graph result, whose equality case is a union of copies of Kd+1.Source: §1 · pp. 2–3
  • The upper and lower bounds extend to the independent set polynomial, equivalently the hard-core model partition function with fugacity λ.The upper-bound equality case remains a disjoint union of complete bipartite graphs; the lower-bound equality case is a disjoint union of cliques.Source: §1 · p. 3
  • For bipartite graphs, the upper-bound polynomial result also allows distinct positive weights λ and µ on the two vertex classes.Equality holds exactly for disjoint unions of complete bipartite graphs.Source: §1 · p. 3
  • The proof strategy adapts an induction approach previously used for maximum degree at most 5, replacing its computer assistance with analytic inequalities.Some technical inequality verifications are deferred to the appendix.Source: §1 · p. 4
  • The paper also discusses degree-distribution extremal bounds and potential applications to counting colorings and graph homomorphisms.The degree-distribution formulation seeks the maximum normalized independent-set count among graphs with a fixed degree-degree distribution.Source: §1 · pp. 2, 4

2. Proof strategy

The proofs use induction on graph size, reducing the upper bound to an inequality around a maximum-degree vertex. For bipartite graphs, distance layers and analytic inequalities make that local comparison tractable.

2. Proof strategy

  • Theorem 1.2 states the inequality i(G) ≤ j(G) for every graph G, without restricting the class of graphs covered by the result.Source: §2 · p. 4
  • For the bipartite upper-bound proof, the bipartite double cover reduces the comparison to bipartite graphs while preserving degrees.The earlier inequality i(G)^2 ≤ i(G × K2) and the identity j(G)^2 = j(G × K2) yield this reduction.Source: §2 · p. 4
  • Induction uses the recurrence splitting independent sets according to whether they contain a chosen vertex w.For a maximum-degree vertex, proving the resulting comparison suffices to complete the induction.Source: §2 · p. 4
  • Distance layers around w reduce the key inequality to the subgraph induced by V0 ∪ V1 ∪ V2 ∪ V3.The proof analyzes the edge sets between consecutive layers and applies Hölder’s inequality to the resulting quantities.Source: §2 · pp. 4–6

3. Lower bound

The lower-bound proof uses induction and degree comparisons to establish a weighted bound on the independent set polynomial. Equality holds precisely for disjoint unions of cliques.

3. Lower bound

  • The proof proceeds by induction and reduces the connected case to a comparison around a maximum-degree vertex.The polynomial factors over connected components, allowing the proof to assume G is connected.Source: §3 · p. 6
  • Replacing neighborhood degrees by the maximum degree yields the local comparison used to prove the lower bound.The argument allows real degrees in [1, Δ] and iteratively replaces each variable by Δ.Source: §3 · p. 7
  • Equality forces every neighbor of the maximum-degree vertex to have degree Δ and leaves no vertices at distance two.The resulting connected graph is K_(Δ+1), which gives the stated clique equality cases.Source: §3 · p. 7
  • Theorem 1.7’s lower bound is tight exactly when G is a disjoint union of cliques.For connected graphs the inequality is strict except for cliques.Source: §3 · pp. 6–7

4. Upper bound

The upper-bound proof establishes a weighted comparison for bipartite graphs, then uses the bipartite double cover to obtain the general upper-bound results. Equality holds for disjoint unions of complete bipartite graphs.

4. Upper bound

  • Theorem 1.6 yields Theorems 1.5 and 1.2 by setting μ = λ and applying the bipartite double-cover inequality.The double-cover reduction allows the proof to establish the general bound from the bipartite case.Source: §4 · pp. 7, 10
  • The proof uses induction around a maximum-degree vertex and compares contributions from successive distance layers.Hölder’s inequality is applied to the layer-based comparison, with analytic inequalities covering the resulting degree terms.Source: §4 · pp. 8–10
  • Theorem 1.6’s upper bound is tight exactly for disjoint unions of complete bipartite graphs.For connected graphs, equality occurs only for complete bipartite graphs.Source: §4 · pp. 7, 10

5. Further remarks

The further remarks derive degree-distribution extrema and independence-number bounds, then discuss extensions to colorings and graph homomorphisms. The paper also notes that follow-up work proved the conjectures mentioned in this discussion.

5.1. Degree conditions.

  • For a fixed degree distribution, disjoint unions of cliques attain the minimum normalized independent set polynomial.The maximum is attained by complete bipartite components pairing largest and smallest degrees successively, subject to appropriate divisibility conditions.Source: §5.1 · p. 11
  • Similar procedures give extrema under minimum-, average-, or maximum-degree constraints, but their expressions are omitted.For the degree-distribution maximum, the pairing recursion terminates after finitely many steps as the support strictly shrinks.Source: §5.1 · p. 11

5.2. Bounds on independence number.

  • Taking λ to infinity in the lower bound yields the Caro–Wei bound on the independence number.The passage identifies this bound with Caro–Wei and notes that Turán’s theorem follows by convexity.Source: §5.2 · p. 11

5.3. Extensions to colorings and graph homomorphisms.

  • The discussion extends the independent-set framework to colorings and graph homomorphisms, where generalizing the methods requires a different recursion.List-colorings provide a recursive workaround; the notes added report that follow-up work [23] proved all conjectures mentioned above.Source: §5.3 · pp. 12–13

Appendix A. Some analytic inequalities

Appendix A collects technical inequalities used in the proof of the main theorems. It establishes monotonicity and sign properties, including nonnegativity of r(x, y) for x, y ≥ 1 and conditions for equality in Lemma A.3.

Appendix A. Some analytic inequalities

  • g(x) is strictly decreasing for 0 < x < ∆, so g(x) > 0 throughout that interval when g(∆) = 0.Source: Appendix A · p. 13
  • The function in the argument for inequality (17) is shown to be strictly log-concave on (0, ∞).Source: Appendix A · p. 13
  • The function in Lemma A.2 is nondecreasing on (0, ∞) under the stated parameter conditions.The lemma states β ≥ α > 0 and λ, µ ≥ 0.Source: Appendix A · p. 14
  • r(x, y) ≥ 0 for x, y ≥ 1, as required in the appendix’s inequality argument.The proof checks that an auxiliary function is nonpositive, with equality at both endpoints.Source: Appendix A · p. 14
  • The cited passage states that equality holds if and only if at least one of the following conditions is met: v = 1, w = u, or c1c2 = 0.When c1, c2 > 0 and v > 1, equality holds exactly when w = u.Source: Appendix A · pp. 15, 17
Loading 1805.04021v3…