ﻻ يوجد ملخص باللغة العربية
We make the first step towards a nerve theorem for graphs. Let $G$ be a simple graph and let $mathcal{F}$ be a family of induced subgraphs of $G$ such that the intersection of any members of $mathcal{F}$ is either empty or connected. We show that if the nerve complex of $mathcal{F}$ has non-vanishing homology in dimension three, then $G$ contains the complete graph on five vertices as a minor. As a consequence we confirm a conjecture of Goaoc concerning an extension of the planar $(p,q)$ theorem due to Alon and Kleitman: Let $mathcal{F}$ be a finite family of open connected sets in the plane such that the intersection of any members of $mathcal{F}$ is either empty or connected. If among any $p geq 3$ members of $mathcal{F}$ there are some three that intersect, then there is a set of $C$ points which intersects every member of $mathcal{F}$, where $C$ is a constant depending only on $p$.
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
The cut-rank of a set $X$ in a graph $G$ is the rank of the $Xtimes (V(G)-X)$ submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets $(X,Y)$ such that the cut-rank of $X$ is less than $2$ and b
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
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width.
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,