2018/11/05 by Ross S. Berkowitz, Berkowitz, Ross, Pat Devlin +7
Computer Science · Mathematics · #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1811.02018
openalex publication_date 2018/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G and p ∈ [0,1], let Gp denote the random subgraph of G obtained by keeping each edge independently with probability p. Alon, Krivelevich, and Sudokov proved 𝔼 [χ(Gp)] ≥ Cp (χ(G))/(log |V(G)|), and Bukh conjectured an improvement of 𝔼[χ(Gp)] ≥ Cp (χ(G))/(log χ(G)). We prove a new spectral lower bound on 𝔼[χ(Gp)], as progress towards Bukh's conjecture. We also propose the stronger conjecture that for any fixed p ≤ 1/2, among all graphs of fixed chromatic number, 𝔼[χ(Gp)] is minimized by the complete graph. We prove this stronger conjecture when G is planar or χ(G) < 4. We also consider weaker lower bounds on 𝔼[χ(Gp)] proposed in a recent paper by Shinkar; we answer two open questions of Shinkar negatively and propose a possible refinement of one of them.