Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtremal density for sparse minors and subdivisions
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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. Among 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.
rate research
Read More
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 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 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 operation 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.
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$.
In this paper, we show that two balanced triangulations of a closed surface are not necessary connected by a sequence of balanced stellar subdivisions and welds. This answers a question posed by Izmestiev, Klee and Novik. We also show that two balanced triangulations of a closed surface are connected by a sequence of three local operations, which we call the pentagon contraction, the balanced edge subdivision and the balanced edge weld. In addition, we prove that two balanced triangulations of the 2-sphere are connected by a sequence of pentagon contractions and their inverses if none of them are octahedral spheres.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
