On the excess of vertex-transitive graphs of given degree and girth

We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive $k$-regular graphs of girth $g$. Counting cycles to obtain necessary arithmetic conditions on the parameters $(k,g)$, we extend previous results of Biggs, and prove that, for any given excess $e$ and any given degree $k\ge 4$, the asymptotic density of the set of girths $g$ for which there exists a vertex-transitive $(k,g)$-cage with excess not exceeding $e$ is 0.     

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that $\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group ${\mathsf{D}}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\Gamma$ of $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set $T_n$. In particular, $\Gamma$ is a $2(n?2)$-regular graph whose automorphism group is ${\mathsf{D}}_{n+1},$ $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, and its subgraph $\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of ${\mathsf{D}}_{n+1}$ of order $n+1$ with regular Cayley maps on ${\text{Sym}}_n$ is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\text{Sym}}_n$.     

Denjoy minimal sets and Birkhoff periodic orbits for non-exact monotone twist maps

A non-exact monotone twist map ${\overline{\phi }}_F$ is a composition of an exact monotone twist map $\overline{\phi }$ with a generating function H and a vertical translation $V_F$ with $V_F((x,y))=(x,y?F)$. We show in this paper that for each $\omega \in \mathbb{R}$, there exists a critical value $F_d(\omega )\ge 0$ depending on H and ω such that for $0\le F\le F_d(\omega )$, the non-exact twist map ${\overline{\phi }}_F$ has an invariant Denjoy minimal set with irrational rotation number ω lying on a Lipschitz graph, or Birkhoff $(p,q)$-periodic orbits for rational $\omega =p/q$. Like the Aubry–Mather theory, we also construct heteroclinic orbits connecting Birkhoff periodic orbits, and show that quasi-periodic orbits in these Denjoy minimal sets can be approximated by periodic orbits. In particular, we demonstrate that at the critical value $F=F_d(\omega )$, the Denjoy minimal set is not uniformly hyperbolic and can be approximated by smooth curves.     

Fixed points of n-valued maps,the fixed point property and the case of surfaces—A braid approach

We study the fixed point theory of $n$-valued maps of a space $X$ using the fixed point theory of maps between $X$ and its configuration spaces. We give some general results to decide whether an $n$-valued map can be deformed to a fixed point free $n$-valued map. In the case of surfaces, we provide an algebraic criterion in terms of the braid groups of $X$ to study this problem. If $X$ is either the $k$-dimensional ball or an even-dimensional real or complex projective space, we show that the fixed point property holds for $n$-valued maps for all $n\ge 1$, and we prove the same result for even-dimensional spheres for all $n\ge 2$. If $X$ is the $2$-torus, we classify the homotopy classes of $2$-valued maps in terms of the braid groups of $X$. We do not currently have a complete characterisation of the homotopy classes of split $2$-valued maps of the $2$-torus that contain a fixed point free representative, but we give an infinite family of such homotopy classes.     

Uniqueness of Fq-quadratic perfect nonlinear maps from Fq3 to Fq2

Let q be a power of an odd prime. We prove that all ${\mathbb{F}}_q$-quadratic perfect nonlinear maps from ${\mathbb{F}}_{q^3}$ to ${\mathbb{F}}_q^2$ are equivalent. We also give a geometric method to find the corresponding equivalence explicitly.     

Cubic non-normal Cayley graphs of order 4p2

A Cayley graph $\mathrm{Cay}(G,S)$ on a group $G$ is said to be normal if the right regular representation $R\left(G\right)$ of $G$ is normal in the full automorphism group of $\mathrm{Cay}(G,S)$. In this paper all connected cubic non-normal Cayley graphs of order $4p^2$ are constructed explicitly for each odd prime $p$. It is shown that there are three infinite families of cubic non-normal Cayley graphs of order $4p^2$ with $p$ odd prime. Note that a complete classification of cubic non-Cayley vertex-transitive graphs of order $4p^2$ was given in [K. Kutnar, D. Marus?ic?, C. Zhang, On cubic non-Cayley vertex-transitive graphs, J. Graph Theory 69 (2012) 77–95]. As a result, a classification of cubic vertex-transitive graphs of order $4p^2$ can be deduced.     

Game of cops and robbers in oriented quotients of the integer grid

The integer grid $\mathbb{Z}\square \mathbb{Z}$ has four typical orientations of its edges which make it a vertex-transitive digraph. In this paper we analyze the game of Cops and Robbers on arbitrary finite quotients of these directed grids.     

On the number of closed walks in vertex-transitive graphs

The results of Širáň and the first author [A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994) 105–114; More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin. 14 (1996) 121–132] are generalized, and new formulas for the number of closed walks of length $p^r$ or pq, where p and q are primes, valid for all vertex-transitive graphs are found. Based on these formulas, several simple tests for vertex-transitivity are presented, as well as lower bounds on the orders of the smallest vertex- and arc-transitive groups of automorphisms for vertex-transitive graphs of given valence.     

Singularités canoniques et actions horosphériques

Let G be a connected reductive linear algebraic group. We consider the normal G-varieties with horospherical orbits. In this short note, we provide a criterion to determine whether these varieties have at most canonical, log canonical or terminal singularities in the case where they admit an algebraic curve as rational quotient. This result seems to be new in the special setting of torus actions with general orbits of codimension 1. For the given G-variety X, our criterion is expressed in terms of a weight function ${\omega }_X$ that is constructed from the set of G-invariant valuations of the function field $k(X)$. In the log terminal case, the generating function of ${\omega }_X$ coincides with the stringy motivic volume of X. As an application, we discuss the case of normal $k^{?}$-surfaces.     

Mutually describing multisets and integer partitions

To each finite multiset $A$, with underlying set $S\left(A\right)$, we associate a new multiset $d\left(A\right)$, obtained by adjoining to $S\left(A\right)$ the multiplicities of its elements in $A$. We study the orbits of the map $d$ under iteration, and show that if $A$ consists of nonnegative integers, then its orbit under $d$ converges to a cycle. Moreover, we prove that all cycles of $d$ over $\mathbb{Z}$ are of length at most $3$, and we completely determine them. This amounts to finding all systems of mutually describing multisets. In the process, we are led to introduce and study a related discrete dynamical system on the set of integer partitions of $n$ for each $n\ge 1$.     

Sylow subgraphs in self-complementary vertex transitive graphs

A graph is self-complementary if it is isomorphic to its complement. A graph is vertex transitive if for each choice of vertices u and $v$ there is an automorphism that carries the vertex u to $v$. The number of vertices in a self-complementary vertex-transitive graph must necessarily be congruent to 1 mod 4. However, Muzychuk has shown that if $p^m$ is the largest power of a prime p dividing the order of a self-complementary vertex-transitive graph, then $p^m$ must individually be congruent to 1 mod 4. This is accomplished by establishing the existence of a self-complementary vertex transitive subgraph of order $p^m$, a result reminiscent of the Sylow theorems. This article is a self-contained survey, culminating with a detailed proof of Muzychuk's result.