Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.
Title resolution pending
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
citation-role summary
background 2
method 1
citation-polarity summary
representative citing papers
Transfer theorem converts max-degree independence bounds to average-degree bounds for hereditary uniform hypergraphs, with applications to cycle-free graphs and bounded-clique graphs.
For p = d/n the r-th power has maximum degree ~ log n over (r+1)-fold log and chromatic number sandwiched between the maximum degrees of the floor(r/2) and (r-1) powers plus one (equality at r=2); for d = omega(log n) up to n^{1/r-Omega(1)} the chromatic number is Theta(d^r / log d).
Improved fractional chromatic number bounds for d-degenerate locally r-colorable graphs as O(d log(2r)/log d) and for girth-4 r-uniform hypergraphs as c_r (d/log d)^{1/(r-1)} via entropy methods.
New degree-sequence lower bounds on hard-core independent set sizes via multivariate local occupancy and spectral analysis.
citing papers explorer
-
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.
-
Hypergraph independence bounds: from maximum degree to average degree
Transfer theorem converts max-degree independence bounds to average-degree bounds for hereditary uniform hypergraphs, with applications to cycle-free graphs and bounded-clique graphs.
-
Coloring powers of random graphs
For p = d/n the r-th power has maximum degree ~ log n over (r+1)-fold log and chromatic number sandwiched between the maximum degrees of the floor(r/2) and (r-1) powers plus one (equality at r=2); for d = omega(log n) up to n^{1/r-Omega(1)} the chromatic number is Theta(d^r / log d).
-
Fractional coloring via entropy
Improved fractional chromatic number bounds for d-degenerate locally r-colorable graphs as O(d log(2r)/log d) and for girth-4 r-uniform hypergraphs as c_r (d/log d)^{1/(r-1)} via entropy methods.
-
Degree-sequence bounds for independent sets via multivariate local occupancy
New degree-sequence lower bounds on hard-core independent set sizes via multivariate local occupancy and spectral analysis.
- Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)