pith. sign in

arxiv: 1903.03908 · v1 · pith:2BMK6NIHnew · submitted 2019-03-10 · 🧮 math.CO

Asymptotic Density of Graphs Excluding Disconnected Minors

classification 🧮 math.CO
keywords inftygraphsfracasymptoticcontainingdensitydisconnectedgraph
0
0 comments X
read the original abstract

For a graph $H$, let $$c_{\infty}(H)= \lim_{n \to \infty}\max\frac{|E(G)|}{n},$$ where the maximum is taken over all graphs $G$ on $n$ vertices not containing $H$ as a minor. Thus $c_{\infty}(H)$ is the asymptotic maximum density of graphs not containing $H$ as a minor. Employing a structural lemma due to Eppstein, we prove new upper bounds on $c_{\infty}(H)$ for disconnected graphs $H$. In particular, we determine $c_{\infty}(H)$ whenever $H$ is union of cycles. Finally, we investigate the behaviour of $c_\infty(sK_r)$ for fixed $r$, where $sK_r$ denotes the union of $s$ disjoint copies of the complete graph on $r$ vertices. Improving on a result of Thomason, we show that $$c_\infty(sK_r)=s(r-1)-1 \mathrm{\; for \;} s ={\Omega}\left(\frac{\log{r}}{\log\log{r}}\right),$$ and $$c_\infty(sK_r)>s(r-1)-1 \mathrm{\; for \;} s ={o}\left(\frac{\log{r}}{\log\log{r}}\right).$$

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.