1 citations · 1 across the 1 of their papers we have counts for
4 papers
Optimal Hardness of Online Algorithms for Large Independent Sets
David Gamarnik, Eren C. Kızıldağ, Lutz Warnke
We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph . For constant and , the largest independent set has si…
The clique chromatic number of sparse random graphs
Manuel Fernandez, Lutz Warnke
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In this paper, we determine the order of ma…
Two-Point Concentration of the Domination Number of Random Graphs
Tom Bohman, Lutz Warnke, Emily Zhu
We show that the domination number of the binomial random graph G_{n,p} with edge-probability p is concentrated on two values for p \ge n^{-2/3+\eps}, and not concentrated on two v…
Extreme local statistics in random graphs: maximum tree extension counts
Pedro Araújo, Simon Griffiths, Matas Šileikis +1
We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = \max_v X_v where X_v counts the number of copies of a given tree in G_{n,p} rooted at ver…