2024/07/16 by Maurício Collares, Sahar Diskin, Collares, Maurício +5 · 1 citation
Economics, Econometrics and Finance · #Combinatorics (math.CO) #Economic Theory and Policy #FOS: Mathematics #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2407.11495
openalex publication_date 2024/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G and probability p, we form the random subgraph Gp by retaining each edge of G independently with probability p. Given d∈ℕ and constants 00, we show that if every subset S⊆ V(G) of size exactly (c|V(G)|)/(d) satisfies |N(S)|≥ d|S| and p=(1+ε)/(d), then the probability that Gp does not contain a cycle of length Ω(ε2c2|V(G)|) is exponentially small in |V(G)|. As an intermediate step, we also show that given k,d∈ ℕ and a constant ε>0, if every subset S⊆ V(G) of size exactly k satisfies |N(S)|≥ kd and p=(1+ε)/(d), then the probability that Gp does not contain a path of length Ω(ε2 kd) is exponentially small. We further discuss applications of these results to Ks,t-free graphs of maximal density.