Regular induced subgraphs of a random graph

Simple item page
dc.creatorKrivelevich, Michael
dc.creatorSudakov, Benny
dc.creatorWormald, Nicholas
dc.date2008-08-14
dc.date.accessioned2026-07-07T09:56:41Z
dc.date.available2026-07-07T09:56:41Z
dc.descriptionAn old problem of Erdős, Fajtlowicz and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on n vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on n vertices, i.e., in a binomial random graph G(n,1/2). We prove that with high probability a largest induced regular subgraph of G(n,1/2) has about n^{2/3} vertices.
dc.identifierhttps://arxiv.org/abs/0808.2023
dc.identifierhttp://arxiv.org/abs/0808.2023
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/167062
dc.subjectCombinatorics
dc.subjectProbability
dc.titleRegular induced subgraphs of a random graph
dc.typetext

Files

Collections

arXiv