اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExtremal functions for sparse minors
426
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the density of a graph $G$ is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$, as well as almost all graphs $H$ of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$, $$c(H) = (1+o(1))cdotmaxleft{frac{|V(H)|}{2},|V(H)| - alpha (H)right},$$ extending recent results of Haslegrave, Kim and Liu (2020). We also show that an asymptotically tight bound on the extremal function of graphs in minor-closed families proposed by Haslegrave, Kim and Liu (2020) is equivalent to a well studied open weakening of Hadwigers conjecture.
قيم البحث
اقرأ أيضاً
We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood on embedding sparse minors. A
mong others, $bullet$ $(1+o(1))t^2$ average degree is sufficient to force the $ttimes t$ grid as a topological minor; $bullet$ $(3/2+o(1))t$ average degree forces every $t$-vertex planar graph as a minor, and the constant $3/2$ is optimal, furthermore, surprisingly, the value is the same for $t$-vertex graphs embeddable on any fixed surface; $bullet$ a universal bound of $(2+o(1))t$ on average degree forcing every $t$-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.
We prove that every graph with $n$ vertices and at least $5n-8$ edges contains the Petersen graph as a minor, and this bound is best possible. Moreover we characterise all Petersen-minor-free graphs with at least $5n-11$ edges. It follows that every
graph containing no Petersen minor is 9-colourable and has vertex arboricity at most 5. These results are also best possible.
We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $Gamma$ the generalized Turan density $pi_F(Gamma)$ denotes the density of a maximum subgraph of $Gamma$, which contains no copy of~$F$. Extending classical Turan
type results for odd cycles, we show that $pi_{F}(Gamma)=1/2$ provided $F$ is an odd cycle and $Gamma$ is a sufficiently pseudorandom graph. In particular, for $(n,d,lambda)$-graphs $Gamma$, i.e., $n$-vertex, $d$-regular graphs with all non-trivial eigenvalues in the interval $[-lambda,lambda]$, our result holds for odd cycles of length $ell$, provided [ lambda^{ell-2}ll frac{d^{ell-1}}nlog(n)^{-(ell-2)(ell-3)},. ] Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabo, and Vu, who addressed the case when $F$ is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free $(n,d,lambda)$-graphs) shows that our assumption on $Gamma$ is best possible up to the polylog-factor for every odd $ellgeq 5$.
We show that for pairs $(Q,R)$ and $(S,T)$ of disjoint subsets of vertices of a graph $G$, if $G$ is sufficiently large, then there exists a vertex $v$ in $V(G)-(Qcup Rcup Scup T)$ such that there are two ways to reduce $G$ by a vertex-minor operatio
n while preserving the connectivity between $Q$ and $R$ and the connectivity between $S$ and $T$. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids.
Frame matroids and lifted-graphic matroids are two distinct minor-closed classes of matroids, each of which generalises the class of graphic matroids. The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, simultane
ously generalises both the classes of frame and lifted-graphic matroids. Let $mathcal{M}$ be one of these three classes, and let $r$ be a positive integer. We show that $mathcal{M}$ has only a finite number of excluded minors of rank $r$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
