Full subgraphs

DOI10.1002/JGT.22221MaRDI QIDQ4581273zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1505.03072

zbMATH Keywords

extremal graph theorygraph discrepancygraph partitions

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $ngeq2$, [ (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^{-frac23}<p_n<1-n^{-frac17}$, [ 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 $p$ near the elements of $frac12,frac23,frac34,dots$. In contrast, we show that for any $n$-vertex graph $G$, either $G$ or $G^c$ contains a full subgraph on $Omega(fracnlogn)$ vertices. Finally, we discuss full subgraphs of random and pseudo-random graphs, and several open problems.

Recommendations

• scientific article; zbMATH DE number 747033
• scientific article; zbMATH DE number 969094
• Subgraphs of minimal degree \(k\)
• On Subgraph Sizes in Random Graphs
• Dense subgraphs in random graphs

Cited in

(3)

• Locally sparse graph with large density
• Asymptotic enumeration of full graphs
• Subgraph complementation

This page was built for publication: Full subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581273)