Geodesic
A lower bound on the average degree forcing a minor
Sergey Norin1 ; Bruce Reed ; Andrew Thomason ; David R. Wood
1McGill University
The electronic journal of combinatorics, Tome 27 (2020) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We show that for sufficiently large $d$ and for $t\geq d+1$, there is a graph $G$ with average degree $(1-\varepsilon)\lambda t \sqrt{\ln d}$ such that almost every graph $H$ with $t$ vertices and average degree $d$ is not a minor of $G$, where $\lambda=0.63817\dots$ is an explicitly defined constant. This generalises analogous results for complete graphs by Thomason (2001) and for general dense graphs by Myers and Thomason (2005). It also shows that an upper bound for sparse graphs by Reed and Wood (2016) is best possible up to a constant factor.
DOI : 10.37236/8847
Classification : 05C83, 05C35, 05C80, 05C42
Mots-clés : subcontraction, random graph, pseudo-random graph, extremal graph

Sergey Norin  1   ; Bruce Reed    ; Andrew Thomason    ; David R. Wood 

1 McGill University 
@article{10_37236_8847,
     author = {Sergey Norin and Bruce Reed and Andrew Thomason and David R. Wood},
     title = {A lower bound on the average degree forcing a minor},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {2},
     doi = {10.37236/8847},
     zbl = {1442.05218},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8847/}
}
TY  - JOUR
AU  - Sergey Norin
AU  - Bruce Reed
AU  - Andrew Thomason
AU  - David R. Wood
TI  - A lower bound on the average degree forcing a minor
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8847/
DO  - 10.37236/8847
ID  - 10_37236_8847
ER  - 
%0 Journal Article
%A Sergey Norin
%A Bruce Reed
%A Andrew Thomason
%A David R. Wood
%T A lower bound on the average degree forcing a minor
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8847/
%R 10.37236/8847
%F 10_37236_8847
Sergey Norin; Bruce Reed; Andrew Thomason; David R. Wood. A lower bound on the average degree forcing a minor. The electronic journal of combinatorics, Tome 27 (2020) no. 2. doi: 10.37236/8847

Cité par Sources :