Cover Image

Large deviations of the greedy independent set algorithm on sparse random graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Kolesnik, Brett
Format:	Preprint
Published:	2020
Subjects:	Probability Combinatorics 05C80, 05C85, 49M25, 60F10, 65N22, 68W40
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sharp Fuss-Catalan thresholds in graph bootstrap percolation
by: Bartha, Zsolt, et al.
Published: (2025)

Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
by: Diaconis, Persi, et al.
Published: (2019)

Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs
by: Diamond, Harvey, et al.
Published: (2024)

Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs
by: Diamond, Harvey, et al.
Published: (2024)

Thresholds for contagious sets in random graphs
by: Angel, Omer, et al.
Published: (2016)

$H$-percolation with a random $H$
by: Bartha, Zsolt, et al.
Published: (2023)

A note on limits of sequences of binary trees
by: Grübel, Rudolf
Published: (2023)

The largest subcritical component in inhomogeneous random graphs of preferential attachment type
by: Mörters, Peter, et al.
Published: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

Majority dynamics on sparse random graphs
by: Chakraborti, Debsoumya, et al.
Published: (2021)

Asymptotic size of the Karp-Sipser Core in Configuration Model
by: Chatterjee, Arnab, et al.
Published: (2025)

On Conjectures concerning the Labeled Coupon Collector Problem
by: Barak-Pelleg, Dina, et al.
Published: (2025)

Local limit of Prim's algorithm
by: Corsini, Benoît, et al.
Published: (2025)

Isomorphisms between random $d$-hypergraphs
by: Lenoir, Théo
Published: (2024)

On the Average-Case Performance of Greedy for Maximum Coverage
by: Balkanski, Eric, et al.
Published: (2026)

Normal approximation for subgraph count in random hypergraphs
by: Michalczuk, Wojciech, et al.
Published: (2024)

The law of the circumference of sparse binomial random graphs
by: Anastos, Michael, et al.
Published: (2025)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Zero-free regions of partition functions with applications to algorithms and graph limits
by: Regts, Guus
Published: (2015)

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
by: Galby, Esther, et al.
Published: (2024)

Note on down-set thresholds
by: Warnke, Lutz
Published: (2023)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

The spread of fire on a random multigraph
by: Goldschmidt, Christina, et al.
Published: (2017)

Maximum number of points in general position in a random subset of finite $3$-dimensional spaces
by: Balogh, József, et al.
Published: (2025)

The degree-restricted random process is far from uniform
by: Molloy, Michael, et al.
Published: (2022)

The clique chromatic number of sparse random graphs
by: Fernandez V, Manuel, et al.
Published: (2024)

On the thresholds of degenerate hypergraphs
by: Chen, Yu, et al.
Published: (2024)

Scaling limits of random graphs
by: Addario-Berry, Louigi, et al.
Published: (2024)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

On 3-colorability of (claw, diamond)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2026)

Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution
by: Müller, Noela, et al.
Published: (2024)

Universal diameter bounds for random graphs with given degrees
by: Addario-Berry, Louigi, et al.
Published: (2025)

The number and structure of connected graphs with a fixed degree sequence
by: Bell, Sasha, et al.
Published: (2026)

The critical activation density in graph bootstrap percolation
by: Kolesnik, Brett, et al.
Published: (2026)

$d$-connectivity of the random graph with restricted budget
by: Lichev, Lyuben
Published: (2022)

Random cliques in random graphs revisited
by: Morris, Robert, et al.
Published: (2025)

Large graph limits of local matching algorithms on Configuration model graphs
by: Aoudi, Mohamed Habib Aliou Diallo, et al.
Published: (2024)

Weakly saturated random graphs
by: Bartha, Zsolt, et al.
Published: (2020)

Isomorphisms between dense random graphs
by: Surya, Erlang, et al.
Published: (2023)