Search

We consider non-degenerate graph immersions into affine space $\mathbb A^{n+1}$ whose cubic form is parallel with respect to the Levi-Civita connection of the affine metric. There exists a correspondence between such graph immersions and pairs $(J,\gamma)$, where $J$ is an $n$-dimensional real Jordan algebra and $\gamma$ is a non-degenerate trace form on $J$. Every graph immersion with parallel cubic form can be extended to an affine complete symmetric space covering the maximal connected component of zero in the set of quasi-regular elements in the algebra $J$. It is an improper affine hypersphere if and only if the corresponding Jordan algebra is nilpotent. In this case it is an affine complete, Euclidean complete graph immersion, with a polynomial as globally defining function. We classify all such hyperspheres up to dimension 5. As a special case we describe a connection between Cayley hypersurfaces and polynomial quotient algebras. Our algebraic approach can be used to study also other classes of hypersurfaces with parallel cubic form., Comment: some proofs have been simplified with respect to the first version

If $f : \tilde{\Gamma} \rightarrow \Gamma$ is a covering map between connected graphs, and $H$ is the subgroup of $\pi_1(\Gamma,v)$ used to construct the cover, then it is well known that the group of deck transformations of the cover is isomorphic to $ N(H)/H$, where $N(H)$ is the normalizer of $H$ in $\pi_1(\Gamma,v)$. We show that an entirely analogous result holds for immersions between connected graphs, where the subgroup $H$ is replaced by the closed inverse submonoid of the inverse monoid $L(\Gamma,v)$ used to construct the immersion. We observe a relationship between group actions on graphs and deck transformations of graph immersions. We also show that a graph immersion $f : \tilde{\Gamma} \rightarrow \Gamma$ may be extended to a cover $g : \tilde{\Delta} \rightarrow \Gamma$ in such a way that all deck transformations of $f$ are restrictions of deck transformations of $g$., Comment: 19 pages, 3 figures

An immersion of a graph H in another graph G is a one-to-one mapping phi:V(H)->V(G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P_{uv} corresponding to the edge uv has endpoints phi(u) and phi(v). The immersion is strong if the paths P_{uv} are internally disjoint from phi(V(H)). We prove that every simple graph of minimum degree at least 11t+7 contains a strong immersion of the complete graph K_t. This improves on previously known bound of minimum degree at least 200t obtained by DeVos et al., 12 pages, 1 figure

In this article we consider the relationship between vertex coloring and the immersion order. Specifically, a conjecture proposed by Abu-Khzam and Langston in 2003, which says that the complete graph with t vertices can be immersed in any t -chromatic graph, is studied. First, we present a general result about immersions and prove that the conjecture holds for graphs whose complement does not contain any induced cycle of length four and also for graphs having the property that every set of five vertices induces a subgraph with at least six edges. Then, we study the class of all graphs with independence number less than three, which are graphs of interest for Hadwiger’s Conjecture. We study such graphs for the immersion-analog. If Abu-Khzam and Langston’s conjecture is true for this class of graphs, then an easy argument shows that every graph of independence number less than 3 contains K n 2 as an immersion. We show that the converse is also true. That is, if every graph with independence number less than 3 contains an immersion of K n 2 , then Abu-Khzam and Langston’s conjecture is true for this class of graphs. Furthermore, we show that every graph of independence number less than 3 has an immersion of K n 3 .

The relationship between covering spaces of graphs and subgroups of the free group leads to a rapid proof of the Nielsen-Schreier subgroup theorem. We show here that a similar relationship holds between immersions of graphs and closed inverse submonoids of free inverse monoids. We prove using these methods, that a closed inverse submonoid of a free inverse monoid is finitely generated if and only if it has finite index if and only if it is a rational subset of the free inverse monoid in the sense of formal language theory. We solve the word problem for the free inverse category over a graph Γ. We show that immersions over Γ may be classified via conjugacy classes of loop monoids of the free inverse category over Γ. In the case that Γ is a bouquet of X circles, we prove that the category of (connected) immersions over Γ is equivalent to the category of (transitive) representations of the free inverse monoid FIM(X). Such representations are coded by closed inverse submonoids of FIM(X). These monoids will be constructed in a natural way from groups acting freely on trees and they admit an idempotent pure retract onto a free inverse monoid. Applications to the classification of finitely generated subgroups of free groups via finite inverse monoids are developed.

Building on recent work of Dvo\v{r}\'ak and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t + 4$ contains $K_t$ as an immersion. We also show that every graph on $n$ vertices with no stable set of size three contains $K_{2\lfloor n/5 \rfloor}$ as an immersion., Comment: 26 pages, 1 figure

A graph $H$ is an immersion of a graph $G$ if $H$ can be obtained by some sugraph $G$ after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bbb{N}\rightarrow\Bbb{N}$, such that if $H$ is a connected planar subcubic graph on $h>0$ edges, $G$ is a graph, and $k$ is a non-negative integer, then either $G$ contains $k$ vertex/edge-disjoint subgraphs, each containing $H$ as an immersion, or $G$ contains a set $F$ of $f(k,h)$ vertices/edges such that $G\setminus F$ does not contain $H$ as an immersion.