3 papers
cs.DS2026
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…
math.PR2026
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…
math.CO2025
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…