Search

If $f:\tilde{\unicode[STIX]{x1D6E4}}\rightarrow \unicode[STIX]{x1D6E4}$ is a covering map between connected graphs, and $H$ is the subgroup of $\unicode[STIX]{x1D70B}_{1}(\unicode[STIX]{x1D6E4},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 $\unicode[STIX]{x1D70B}_{1}(\unicode[STIX]{x1D6E4},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(\unicode[STIX]{x1D6E4},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{\unicode[STIX]{x1D6E4}}\rightarrow \unicode[STIX]{x1D6E4}$ may be extended to a cover $g:\tilde{\unicode[STIX]{x1D6E5}}\rightarrow \unicode[STIX]{x1D6E4}$ in such a way that all deck transformations of $f$ are restrictions of deck transformations of $g$. [ABSTRACT FROM AUTHOR]

Abstract: An immersion of a graph H in another graph G is a one‐to‐one mapping ϕ : V ( H ) → V ( G ) and a collection of edge‐disjoint paths in G, one for each edge of H, such that the path P u v corresponding to the edge u v has endpoints ϕ ( u ) and ϕ ( v ). The immersion is strong if the paths P u v are internally disjoint from ϕ ( V ( H ) ). We prove that every simple graph of minimum degree at least 11 t + 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. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu‐Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a K t‐immersion is ( t − 1 )‐colorable. [ABSTRACT FROM AUTHOR]

A graph G contains H as an immersion if there is an injective mapping ϕ : V (H) → V (G) such that for each edge u v ∈ E (H) , there is a path P u v in G joining vertices ϕ (u) and ϕ (v) , and all the paths P u v , u v ∈ E (H) , are pairwise edge-disjoint. An analogue of Hadwiger's conjecture for the clique immersions by Lescure and Meyniel, and independently by Abu-Khzam and Langston, states that every graph G contains K χ (G) as an immersion. We prove that for any constant ε > 0 and integers s , t ≥ 2 , there exists d 0 = d 0 (ε , s , t) such that every K s , t -free graph G with d (G) ≥ d 0 contains a clique immersion of order (1 − ε) d (G). This implies that the above-mentioned conjecture is asymptotically true for graphs without a fixed complete bipartite graph. [ABSTRACT FROM AUTHOR]

A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. There is an obvious necessary degree condition for the immersion containment: if G contains H as an immersion, then for every integer k , the number of vertices of degree at least k in G is at least the number of vertices of degree at least k in H. In this paper, we prove that this obvious necessary condition is "nearly" sufficient for graphs with no edge-cut of order 3: for every graph H , every H -immersion free graph with no edge-cut of order 3 can be obtained by an edge-sum of graphs, where each of the summands is obtained from a graph violating the obvious degree condition by adding a bounded number of edges. The condition for having no edge-cut of order 3 is necessary. A simple application of this theorem shows that for every graph H of maximum degree d ≥ 4 , there exists an integer c such that for every positive integer m , there are at most c m unlabeled d -edge-connected H -immersion free m -edge graphs with no isolated vertex, while there are superexponentially many unlabeled (d − 1) -edge-connected H -immersion free m -edge graphs with no isolated vertex. Our structure theorem will be applied in a forthcoming paper about determining the clustered chromatic number of the class of H -immersion free graphs. [ABSTRACT FROM AUTHOR]

A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. In this paper, we prove an edge-variant of the Erdős-Pósa property with respect to the immersion containment in 4-edge-connected graphs. More precisely, we prove that for every graph H , there exists a function f such that for every 4-edge-connected graph G , either G contains k pairwise edge-disjoint subgraphs each containing H as an immersion, or there exists a set of at most f (k) edges of G intersecting all such subgraphs. This theorem is best possible in the sense that the 4-edge-connectivity cannot be replaced by the 3-edge-connectivity. [ABSTRACT FROM AUTHOR]

In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness. This result had many uses and has been extended to several other decompositions. In this paper, we consider tree-cut decompositions, that have been introduced by Wollan (2015) as a possible edge-version of tree decompositions. We show that every graph admits a tree-cut decomposition of minimum width that additionally satisfies an edge-connectivity condition analogous to Thomas' leanness. [ABSTRACT FROM AUTHOR]

This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter tree-cut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded tree-cut width. Our second result shows that EDP parameterized by tree-cut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph. [ABSTRACT FROM AUTHOR]

In this paper, we show that totally screen umbilic, screen conformal and Hopf null hypersurfaces are nonexistent in indefinite Kaehler space forms of nonzero constant holomorphic sectional curvatures. Furthermore, we prove that all totally screen umbilic null hypersurface immersions into indefinite Kaehler space forms are affinely equivalent to graph immersions. [ABSTRACT FROM AUTHOR]

Similar to Nomizu–Pinkall's geometric characterization of the Cayley surface and Hu–Li–Zhang's characterization of the Cayley hypersurface, how can one characterize the generalized Cayley hypersurfaces? In this paper, by the affine α-connection of statistical manifolds, we study affine hypersurfaces with parallel cubic form relative to the affine α-connection. As the main results, we complete the classification of such hypersurfaces if its affine metric is either definite, or Lorentzian with α ≠ −1. Moreover, we give a new characterization of the generalized Cayley hypersurfaces to answer the question. [ABSTRACT FROM AUTHOR]

A digraph G immerses a digraph H if there is an injection f: V(H) → V(G) and a collection of pairwise edge-disjoint directed paths Puv, for uv ∈ E(H), such that Puv starts at f(u) and ends at f(v). We prove that every Eulerian digraph with minimum out-degree t immerses a complete digraph on Ω(t) vertices, thus answering a question of DeVos, McDonald, Mohar and Scheide. [ABSTRACT FROM AUTHOR]

A partial action of a group G on a set X is a weakening of the usual notion of a group action: the function G×X→X that defines a group action is replaced by a partial function; in addition, the existence of g·(h·x) implies the existence of (gh)·x, but not necessarily conversely. Such partial actions are extremely widespread in mathematics, and the main aim of this paper is to prove two basic results concerning them. First, we obtain an explicit description of Exel's universal inverse semigroup [formula], which has the property that partial actions of the group G give rise to actions of the inverse semigroup [formula]. We apply this result to the theory of graph immersions. Second, we prove that each partial group action is the restriction of a universal global group action. We describe some applications of this result to group theory and the theory of E-unitary inverse semigroups. [ABSTRACT FROM AUTHOR]

In this article, we introduce the notion of locally strongly convex centroaffine T-umbilical hypersurfaces, which may be the “simplest” centroaffine hypersurfaces next to the hyperquadrics centered at the origin. These hypersurfaces are proved to be of a conformally flat, quasi-Einstein centroaffine metric and the pseudo-parallel cubic form relative to the Levi-Civita connection of the centroaffine metric. As the main results, we find a geometric characterization of those hypersurfaces as not being of constant sectional curvature, and further classify these hypersurfaces. Meanwhile, for locally strongly convex centroaffine hypersurfaces with pseudo-parallel cubic form, we completely determine the 3-dimensional case, and all dimensions for the conformally flat case. [ABSTRACT FROM AUTHOR]

Let $f\;:\; M\rightarrow \mathbb{C}P^{2}$ be an isometric immersion of a compact surface in the complex projective plane $\mathbb{C}P^{2}$. In this paper, we consider the Helfrich-type functional $\mathcal{H}_{\lambda _{1},\lambda _{2}}(f)=\int _{M}(|H|^{2}+\lambda _{1}+\lambda _{2} C^{2})\textrm{d} M$ , where $\lambda _{1}, \lambda _{2}\in \mathbb{R}$ with $\lambda _{1}\geqslant 0$ , $H$ and $C$ are respectively the mean curvature vector and the Kähler function of $M$ in $\mathbb{C}P^{2}$. The critical surfaces of $\mathcal{H}_{\lambda _{1},\lambda _{2}}(f)$ are called Helfrich surfaces. We compute the first variation of $\mathcal{H}_{\lambda _{1},\lambda _{2}}(f)$ and classify the homogeneous Helfrich tori in $\mathbb{C}P^{2}$. Moreover, we study the Helfrich energy of the homogeneous tori and show the lower bound of the Helfrich energy for such tori. [ABSTRACT FROM AUTHOR]

Several min–max relations in graph theory can be expressed in the framework of the Erdős–Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic. [ABSTRACT FROM AUTHOR]

Birget, Margolis, Meakin and Weil proved that a finitely generated subgroup K of a free group is pure if and only if the transition monoid M (K) of its Stallings automaton is aperiodic. In this paper, we establish further connections between algebraic properties of K and algebraic properties of M (K). We mainly focus on the cases where M (K) belongs to the pseudovariety of finite monoids all of whose subgroups lie in a given pseudovariety of finite groups. We also discuss normal, malnormal and cyclonormal subgroups of F A using the transition monoid of the corresponding Stallings automaton. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the locally strongly convex affine hypersurfaces with semi-parallel cubic form relative to the Levi-Civita connection of affine metric. We obtain two results on such hypersurfaces which admit at most one affine principal curvature of multiplicity one: (1) classify these being not affine hyperspheres; (2) classify these affine hyperspheres with constant scalar curvature. For the latter, by proving the parallelism of their cubic forms we translate the classification into that of affine hypersurfaces with parallel cubic form, which has been completed by Hu-Li-Vrancken (J Differ Geom 87:239–307, 2011). [ABSTRACT FROM AUTHOR]

Magnus’ Freiheitssatz [20] states that if a group is defined by a presentation with m generators and a single cyclically reduced relator, and this relator contains the last generating letter, then the first m - 1 letters freely generate a free subgroup. We study an analogue of this theorem in the Gromov density model of random groups [14], showing a phase transition phenomenon at density d r = min { 1 2 , 1 - log 2 m - 1 (2 r - 1) } with 1 ≤ r ≤ m - 1 : we prove that for a random group with m generators at density d, if d < d r then the first r letters freely generate a free subgroup; whereas if d > d r then the first r letters generate the whole group. This result partially answers a general problem proposed by Gromov in 2003 [15]: existence/nonexistence of non-free subgroups in a random group. [ABSTRACT FROM AUTHOR]

Thermodynamics provides a unified perspective of the thermodynamic properties of various substances. To formulate thermodynamics in the language of sophisticated mathematics, thermodynamics is described by a variety of differential geometries, including contact and symplectic geometries. Meanwhile, affine geometry is a branch of differential geometry and is compatible with information geometry, where information geometry is known to be compatible with thermodynamics. By combining above, it is expected that thermodynamics is compatible with affine geometry and is expected that several affine geometric tools can be introduced in the analysis of thermodynamic systems. In this paper, affine geometric descriptions of equilibrium and nonequilibrium thermodynamics are proposed. For equilibrium systems, it is shown that several thermodynamic quantities can be identified with geometric objects in affine geometry and that several geometric objects can be introduced in thermodynamics. Examples of these include the following: specific heat is identified with the affine fundamental form and a flat connection is introduced in thermodynamic phase space. For nonequilibrium systems, two classes of relaxation processes are shown to be described in the language of an extension of affine geometry. Finally, this affine geometric description of thermodynamics for equilibrium and nonequilibrium systems is compared with a contact geometric description. [ABSTRACT FROM AUTHOR]

This survey is intended to be a fast (and reasonably updated) reference for the theory of Stallings automata and its applications to the study of subgroups of the free group, with the main accent on algorithmic aspects. Consequently, results concerning finitely generated subgroups have greater prominence in the paper. However, when possible, we try to state the results with more generality, including the usually overlooked non-(finitely-generated) case. [ABSTRACT FROM AUTHOR]

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs ( K5 and K3, 3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for [ABSTRACT FROM AUTHOR]

The goal of this mini-workshop is to gather specialists of the dimer, Ising and spanning tree models around recent and ongoing progress in two directions. One is understanding the connection to the spectral curve of these models in the cases when the curve has positive genus. The other is the introduction of universal embeddings associated to these models. We aim to use these new tools to progress in the study of scaling limits. [ABSTRACT FROM AUTHOR]