Full subgraphs

DOI10.1002/JGT.22221zbMATH Open1396.05055arXiv1505.03072OpenAlexW4210243331MaRDI QIDQ4581273FDOQ4581273

Authors: Victor Falgas-Ravry, Klas Markström, J. Verstraëte

Publication date: 16 August 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let

G = (V, E)

be a graph of density

p

on

n

vertices. Following ErdH{o}s, L uczak and Spencer, an

m

-vertex subgraph

H

of

G

is called {em full} if

H

has minimum degree at least

p (m - 1)

. Let

f (G)

denote the order of a largest full subgraph of

G

. If

is a non-negative integer, define [ f(n,p) = min{f(G) : vert V(G)vert = n, vert E(G)vert = p�inom{n}{2} }.] ErdH{o}s, L uczak and Spencer proved that for

n g e q 2

, [ (2n)^{frac{1}{2}} - 2 leq f(n, {frac{1}{2}}) leq 4n^{frac{2}{3}}(log n)^{frac{1}{3}}.] In this paper, we prove the following lower bound: for

n^{- f r a c 23} < p_{n} < 1 - n^{- f r a c 17}

, [ f(n,p) geq frac{1}{4}(1-p)^{frac{2}{3}}n^{frac{2}{3}} -1.] Furthermore we show that this is tight up to a multiplicative constant factor for infinitely many