Source author record

Gabriel Verret

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR Discrete Mathematics math.AG math.NT

Catalog footprint

Research overview

30works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Abelian Varieties with $p$ -rank Zero

There is a well known theorem by Deuring which gives a criterion for when the reduction of an elliptic curve with complex multiplication (CM) by the ring of integers of an imaginary quadratic field has ordinary or supersingular reduction. We generalise this and a similar theorem by Goren in dimension 2, and classify the $p$ -torsion group scheme of the reduction of 3-dimensional abelian varieties with CM by the ring of integers of a cyclic sextic CM field. We also prove a theorem in arbitrary dimension $g$ that distinguishes ordinary and superspecial reduction for abelian varieties with CM by a cyclic CM field of degree $2g$ . As an application, we give algorithms to construct supersingular non-superspecial, and superspecial abelian varieties of dimension 2 (surfaces) and dimension 3, and show that all such varieties have non-integer endomorphisms of small degree.

preprint2020arXiv

Base Graph -- Connection Graph: Dissection and Construction

This paper presents a phenomenon which sometimes occurs in tetravalent bipartite locally dart-transitive graphs, called a Base Graph -- Connection Graph dissection. In this dissection, each white vertex is split into two vertices of valence 2 so that the connected components of the result are isomorphic. Given the Base Graph whose subdivision is isomorphic to each component, and the Connection Graph, which describes how the components overlap, we can, in some cases, provide a construction which can make a graph having such a decomposition. This paper investigates the general phenomenon as well as the special cases in which the connection graph has no more than one edge.

preprint2020arXiv

Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]

Recently, Huang gave a very elegant proof of the Sensitivity Conjecture by proving that hypercube graphs have the following property: every induced subgraph on a set of more than half its vertices has maximum degree at least $\sqrt{d}$ , where $d$ is the valency of the hypercube. This was generalised by Alon and Zheng who proved that every Cayley graph on an elementary abelian $2$ -group has the same property. Very recently, Potechin and Tsang proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We disprove this conjecture by constructing various counterexamples, including an infinite family of Cayley graphs of unbounded valency which admit an induced subgraph of maximum valency $1$ on a set of more than half its vertices.

preprint2020arXiv

Distinguishing numbers of finite $4$ -valent vertex-transitive graphs

The distinguishing number of a graph $G$ is the smallest $k$ such that $G$ admits a $k$ -colouring for which the only colour-preserving automorphism of $G$ is the identity. We determine the distinguishing number of finite $4$ -valent vertex-transitive graphs. We show that, apart from one infinite family and finitely many examples, they all have distinguishing number $2$ .

preprint2020arXiv

Groups for which it is easy to detect graphical regular representations

We say that a finite group G is "DRR-detecting" if, for every subset S of G, either the Cayley digraph Cay(G,S) is a digraphical regular representation (that is, its automorphism group acts regularly on its vertex set) or there is a nontrivial group automorphism phi of G such that phi(S) = S. We show that every nilpotent DRR-detecting group is a p-group, but that the wreath product of two cyclic groups of order p is not DRR-detecting, for every odd prime p. We also show that if G and H are nontrivial groups that admit a digraphical regular representation and either gcd(|G|,|H|) = 1, or H is not DRR-detecting, then the direct product G x H is not DRR-detecting. Some of these results also have analogues for graphical regular representations.

preprint2020arXiv

Three local actions in $6$ -valent arc-transitive graphs

It is known that there are precisely three transitive permutation groups of degree $6$ that admit an invariant partition with three parts of size $2$ such that the kernel of the action on the parts has order $4$ ; these groups are called $A_4(6)$ , $S_4(6d)$ and $S_4(6c)$ . For each $L\in \{A_4(6), S_4(6d), S_4(6c)\}$ , we construct an infinite family of finite connected $6$ -valent graphs $\{Γ_n\}_{n\in \mathbb{N}}$ and arc-transitive groups $G_n \le \rm{Aut}(Γ_n)$ such that the permutation group induced by the action of the vertex-stabiliser $(G_n)_v$ on the neighbourhood of a vertex $v$ is permutation isomorphic to $L$ , and such that $|(G_n)_v|$ is exponential in $|\rm{V}(Γ_n)|$ . These three groups were the only transitive permutation groups of degree at most $7$ for which the existence of such a family was undecided. In the process, we construct an infinite family of cubic $2$ -arc-transitive graphs such that the dimension of the $1$ -eigenspace over the field of order $2$ of the adjacency matrix of the graph grows linearly with the order of the graph.

preprint2016arXiv

Arc-transitive digraphs with quasiprimitive local actions

Let $Γ$ be a finite $G$ -vertex-transitive digraph. The in-local action of $(Γ,G)$ is the permutation group $L_-$ induced by the vertex-stabiliser on the set of in-neighbours of $v$ . The out-local action $L_+$ is defined analogously. Note that $L_-$ and $L_+$ may not be isomorphic. We thus consider the problem of determining which pairs $(L_-,L_+)$ are possible. We prove some general results, but pay special attention to the case when $L_-$ and $L_+$ are both quasiprimitive. (Recall that a permutation group is quasiprimitive if each of its nontrivial normal subgroups is transitive.) Along the way, we prove a structural result about pairs of finite quasiprimitive groups of the same degree, one being (abstractly) isomorphic to a proper quotient of the other.

preprint2016arXiv

Cubic arc-transitive $k$ -circulants

For an integer $k\geq 1$ , a graph is called a $k$ -circulant if its automorphism group contains a cyclic semiregular subgroup with $k$ orbits on the vertices. We show that, if $k$ is even, there exist infinitely many cubic arc-transitive $k$ -circulants. We conjecture that, if $k$ is odd, then a cubic arc-transitive $k$ -circulant has order at most $6k^2$ . Our main result is a proof of this conjecture when $k$ is squarefree and coprime to $6$ .

preprint2016arXiv

Isomorphisms of Cayley graphs on nilpotent groups

Let S be a finite generating set of a torsion-free, nilpotent group G. We show that every automorphism of the Cayley graph Cay(G;S) is affine. (That is, every automorphism of the graph is obtained by composing a group automorphism with multiplication by an element of the group.) More generally, we show that if Cay(G;S) and Cay(G';S') are connected Cayley graphs of finite valency on two nilpotent groups G and G', then every isomorphism from Cay(G;S) to Cay(G';S') factors through to a well-defined affine map from G/N to G'/N', where N and N' are the torsion subgroups of G and G', respectively. For the special case where the groups are abelian, these results were previously proved by A.A.Ryabchenko and C.Loeh, respectively.

preprint2015arXiv

Groups of order at most 6 000 generated by two elements, one of which is an involution, and related structures

A (2,*)-group is a group that can be generated by two elements, one of which is an involution. We describe the method we have used to produce a census of all (2,*)-groups of order at most 6 000. Various well-known combinatorial structures are closely related to (2,*)-groups and we also obtain censuses of these as a corollary.

preprint2015arXiv

On $2$ -arc-transitive graphs of order $kp^n$

We show that there exist functions $c$ and $g$ such that, if $k$ , $n$ and $d$ are positive integers with $d> g(n)$ and $Γ$ is a $d$ -valent $2$ -arc-transitive graph of order $kp^n$ with $p$ a prime, then $p\leqslant kc(d)$ . In other words, there are only finitely many $d$ -valent 2-arc-transitive graphs of order $kp^n$ with $d>g(n)$ and $p$ prime. This generalises a recent result of Conder, Li and Potočnik.

preprint2015arXiv

On the order of Borel subgroups of group amalgams and an application to locally-transitive graphs

A permutation group is called semiprimitive if each of its normal subgroups is either transitive or semiregular. Given nontrivial finite transitive permutation groups $L_1$ and $L_2$ with $L_1$ not semiprimitive, we construct an infinite family of rank two amalgams of permutation type $[L_1,L_2]$ and Borel subgroups of strictly increasing order. As an application, we show that there is no bound on the order of edge-stabilisers in locally $[L_1,L_2]$ graphs. We also consider the corresponding question for amalgams of rank $k\geq 3$ . We completely resolve this by showing that the order of the Borel subgroup is bounded by the permutation type $[L_1,...,L_k]$ only in the trivial case where each of $L_1,...,L_k$ is regular.

preprint2015arXiv

Vertex-primitive digraphs having vertices with almost equal neighbourhoods

We consider vertex-primitive digraphs having two vertices with almost equal neighbourhoods (that is, the set of vertices that are neighbours of one but not the other is small). We prove a structural result about such digraphs and then apply it to answer a question of Araújo and Cameron about synchronising groups.

preprint2014arXiv

Cayley graphs on abelian groups

Let $A$ be an abelian group and let $ι$ be the automorphism of $A$ defined by $i:a\mapsto a^{-1}$ . A Cayley graph $Γ=\mathrm{Cay}(A,S)$ is said to have an automorphism group \emph{as small as possible} if $\mathrm{Aut}(Γ)= A\rtimes\langle i\rangle$ . In this paper, we show that almost all Cayley graphs on abelian groups have automorphism group as small as possible, proving a conjecture of Babai and Godsil.

preprint2014arXiv

Elusive groups of automorphisms of digraphs of small valency

A transitive permutation group is called elusive if it contains no semiregular element. We show that no group of automorphisms of a connected graph of valency at most four is elusive and determine all the elusive groups of automorphisms of connected digraphs of out-valency at most three.

preprint2014arXiv

Semiregular automorphisms of cubic vertex-transitive graphs

We characterise connected cubic graphs admitting a vertex- transitive group of automorphisms with an abelian normal subgroup that is not semiregular. We illustrate the utility of this result by using it to prove that the order of a semiregular subgroup of maximum order in a vertex-transitive group of automorphisms of a connected cubic graph grows with the order of the graph.

preprint2014arXiv

Vertex-transitive CIS graphs

A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. A graph is well-covered if all its maximal stable sets are of the same size, co-well-covered if its complement is well-covered, and vertex-transitive if, for every pair of vertices, there exists an automorphism of the graph mapping one to the other. We show that a vertex-transitive graph is CIS if and only if it is well-covered, co-well-covered, and the product of its clique and stability numbers equals its order. A graph is irreducible if no two distinct vertices have the same neighborhood. We classify irreducible well-covered CIS graphs with clique number at most 3 and vertex-transitive CIS graphs of valency at most 7, which include an infinite family. We also exhibit an infinite family of vertex-transitive CIS graphs which are not Cayley.

preprint2013arXiv

A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two

A complete list of all connected arc-transitive asymmetric digraphs of in-valence and out-valence 2 on up to 1000 vertices is presented. As a byproduct, a complete list of all connected 4-valent graphs admitting a half-arc-transitive group of automorphisms on up to 1000 vertices is obtained. Several graph-theoretical properties of the elements of our census are calculated and discussed.

preprint2013arXiv

Arc-transitive graphs of valency 8 have a semiregular automorphism

One version of the polycirculant conjecture states that every vertex-transitive graph has a semiregular automorphism. We give a proof of the conjecture in the arc-transitive case for graphs of valency 8, which was the smallest open case.

preprint2013arXiv

Automorphisms of Cayley graphs on generalised dicyclic groups

A graph is called a GRR if its automorphism group acts regularly on its vertex-set. Such a graph is necessarily a Cayley graph. Godsil has shown that there are only two infinite families of finite groups that do not admit GRRs : abelian groups and generalised dicyclic groups. Indeed, any Cayley graph on such a group admits specific additional graph automorphisms that depend only on the group. Recently, Dobson and the last two authors showed that almost all Cayley graphs on abelian groups admit no automorphisms other than these obvious necessary ones. In this paper, we prove the analogous result for Cayley graphs on the remaining family of exceptional groups: generalised dicyclic groups.

preprint2013arXiv

On the order of vertex-stabilisers in vertex-transitive graphs with local group $C_p\times C_p$ or $C_p \wr C_2$

Let $p$ be a prime and let $L$ be either the intransitive permutation group $C_p\times C_p$ of degree $2p$ or the transitive permutation group $C_p \wr C_2$ of degree $2p$ . Let $Γ$ be a connected $G$ -vertex-transitive and $G$ -edge-transitive graph and let $v$ be a vertex of $Γ$ . We show that if the permutation group induced by the vertex-stabiliser $G_v$ on the neighbourhood $Γ(v)$ is isomorphic to $L$ then either $|V(Γ)|\geq p|G_v|\log_p\left(|G_v|/2\right)$ , or $|V(Γ)|$ is bounded by a constant depending only on $p$ , or $Γ$ is a very-well understood graph. This generalises a few recent results.

preprint2013arXiv

Semiregular automorphisms of edge-transitive graphs

The polycirculant conjecture asserts that every vertex-transitive digraph has a semiregular automorphism, that is, a nontrivial automorphism whose cycles all have the same length. In this paper we investigate the existence of semiregular automorphisms of edge-transitive graphs. In particular, we show that any regular edge-transitive graph of valency three or four has a semiregular automorphism.

preprint2012arXiv

Asymptotic enumeration of vertex-transitive graphs of fixed valency

Let $G$ be a group and let $S$ be an inverse-closed and identity-free generating set of $G$ . The \emph{Cayley graph} $\Cay(G,S)$ has vertex-set $G$ and two vertices $u$ and $v$ are adjacent if and only if $uv^{-1}\in S$ . Let $CAY_d(n)$ be the number of isomorphism classes of $d$ -valent Cayley graphs of order at most $n$ . We show that $\log(CAY_d(n))\inΘ(d(\log n)^2)$ , as $n\to\infty$ . We also obtain some stronger results in the case $d=3$ .

preprint2012arXiv

Cubic vertex-transitive graphs on up to 1280 vertices

A graph is called cubic and tetravalent if all of its vertices have valency 3 and 4, respectively. It is called vertex-transitive and arc-transitive if its automorphism group acts transitively on its vertex-set and on its arc- set, respectively. In this paper, we combine some new theoretical results with computer calculations to construct all cubic vertex-transitive graphs of order at most 1280. In the process, we also construct all tetravalent arc-transitive graphs of order at most 640.

preprint2012arXiv

On intransitive graph-restrictive permutation groups

Let $Γ$ be a finite connected $G$ -vertex-transitive graph and let $v$ be a vertex of $Γ$ . If the permutation group induced by the action of the vertex-stabiliser $G_v$ on the neighbourhood $Γ(v)$ is permutation isomorphic to $L$ , then $(Γ,G)$ is said to be locally- $L$ . A permutation group $L$ is graph-restrictive if there exists a constant $c(L)$ such that, for every locally- $L$ pair $(Γ,G)$ and a vertex $v$ of $Γ$ , the inequality $|G_v|\leq c(L)$ holds. We show that an intransitive group is graph-restrictive if and only if it is semiregular.

preprint2012arXiv

On the order of arc-stabilisers in arc-transitive graphs with prescribed local group

Let $Γ$ be a connected $G$ -arc-transitive graph, let $uv$ be an arc of $Γ$ and let $L$ be the permutation group induced by the action of the vertex-stabiliser $G_v$ on the neighbourhood $Γ(v)$ . We study the problem of bounding $|G_{uv}|$ in terms of $L$ and the order of $Γ$ .

preprint2011arXiv

Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph

In this paper we discuss a method for bounding the size of the stabiliser of a vertex in a $G$ -vertex-transitive graph $Γ$ . In the main result the group $G$ is quasiprimitive or biquasiprimitive on the vertices of $Γ$ , and we obtain a genuine reduction to the case where $G$ is a nonabelian simple group. Using normal quotient techniques developed by the first author, the main theorem applies to general $G$ -vertex-transitive graphs which are $G$ -locally primitive (respectively, $G$ -locally quasiprimitive), that is, the stabiliser $G_α$ of a vertex $α$ acts primitively (respectively quasiprimitively) on the set of vertices adjacent to $α$ . We discuss how our results may be used to investigate conjectures by Richard Weiss (in 1978) and the first author (in 1998) that the order of $G_α$ is bounded above by some function depending only on the valency of $Γ$ , when $Γ$ is $G$ -locally primitive or $G$ -locally quasiprimitive, respectively.

preprint2011arXiv

On graph-restrictive permutation groups

Let $Γ$ be a connected $G$ -vertex-transitive graph, let $v$ be a vertex of $Γ$ and let $L=G_v^{Γ(v)}$ be the permutation group induced by the action of the vertex-stabiliser $G_v$ on the neighbourhood $Γ(v)$ . Then $(Γ,G)$ is said to be \emph{locally- $L$ }. A transitive permutation group $L$ is \emph{graph-restrictive} if there exists a constant $c(L)$ such that, for every locally- $L$ pair $(Γ,G)$ and an arc $(u,v)$ of $Γ$ , the inequality $|G_{uv}|\leq c(L)$ holds. Using this terminology, the Weiss Conjecture says that primitive groups are graph-restrictive. We propose a very strong generalisation of this conjecture: a group is graph-restrictive if and only if it is semiprimitive. (A transitive permutation group is said to be \emph{semiprimitive} if each of its normal subgroups is either transitive or semiregular.) Our main result is a proof of one of the two implications of this conjecture, namely that graph-restrictive groups are semiprimitive. We also collect the known results and prove some new ones regarding the other implication.

preprint2010arXiv

Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs

The main result of this paper is that, if $Γ$ is a connected 4-valent $G$ -arc-transitive graph and $v$ is a vertex of $Γ$ , then either $Γ$ is one of a well understood infinite family of graphs, or $|G_v|\leq 2^43^6$ or $2|G_v|\log_2(|G_v|/2)\leq |\VΓ|$ and that this last bound is tight. As a corollary, we get a similar result for $3$ -valent vertex-transitive graphs.

preprint2010arXiv

Tetravalent arc-transitive graphs with unbounded vertex-stabilisers

It has long been known that there exist finite connected tetravalent arc-transitive graphs with arbitrarily large vertex-stabilisers. However, beside a well known family of exceptional graphs, related to the lexicographic product of a cycle with an edgeless graph on two vertices, only a few such infinite families of graphs are known. In this paper, we present two more families of tetravalent arc-transitive graphs with large vertex-stabilisers, each significant for its own reason.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Gabriel Verret

Research overview

Is this your work?

30 publications

Abelian Varieties with $p$ -rank Zero

Base Graph -- Connection Graph: Dissection and Construction

Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]

Distinguishing numbers of finite $4$ -valent vertex-transitive graphs

Groups for which it is easy to detect graphical regular representations

Three local actions in $6$ -valent arc-transitive graphs

Arc-transitive digraphs with quasiprimitive local actions

Cubic arc-transitive $k$ -circulants

Isomorphisms of Cayley graphs on nilpotent groups

Groups of order at most 6 000 generated by two elements, one of which is an involution, and related structures

On $2$ -arc-transitive graphs of order $kp^n$

On the order of Borel subgroups of group amalgams and an application to locally-transitive graphs

Vertex-primitive digraphs having vertices with almost equal neighbourhoods

Cayley graphs on abelian groups

Elusive groups of automorphisms of digraphs of small valency

Semiregular automorphisms of cubic vertex-transitive graphs

Vertex-transitive CIS graphs

A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two

Arc-transitive graphs of valency 8 have a semiregular automorphism

Automorphisms of Cayley graphs on generalised dicyclic groups

On the order of vertex-stabilisers in vertex-transitive graphs with local group $C_p\times C_p$ or $C_p \wr C_2$

Semiregular automorphisms of edge-transitive graphs

Asymptotic enumeration of vertex-transitive graphs of fixed valency

Cubic vertex-transitive graphs on up to 1280 vertices

On intransitive graph-restrictive permutation groups

On the order of arc-stabilisers in arc-transitive graphs with prescribed local group

Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph

On graph-restrictive permutation groups

Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs

Tetravalent arc-transitive graphs with unbounded vertex-stabilisers

See the researcher in context

Building this map preview

Gabriel Verret

Research overview

Is this your work?

30 publications

Abelian Varieties with ppp-rank Zero

Base Graph -- Connection Graph: Dissection and Construction

Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]

Distinguishing numbers of finite 444-valent vertex-transitive graphs

Groups for which it is easy to detect graphical regular representations

Three local actions in 666-valent arc-transitive graphs

Arc-transitive digraphs with quasiprimitive local actions

Cubic arc-transitive kkk-circulants

Isomorphisms of Cayley graphs on nilpotent groups

Groups of order at most 6 000 generated by two elements, one of which is an involution, and related structures

On 222-arc-transitive graphs of order kpnkp^nkpn

On the order of Borel subgroups of group amalgams and an application to locally-transitive graphs

Vertex-primitive digraphs having vertices with almost equal neighbourhoods

Cayley graphs on abelian groups

Elusive groups of automorphisms of digraphs of small valency

Semiregular automorphisms of cubic vertex-transitive graphs

Vertex-transitive CIS graphs

A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two

Arc-transitive graphs of valency 8 have a semiregular automorphism

Automorphisms of Cayley graphs on generalised dicyclic groups

On the order of vertex-stabilisers in vertex-transitive graphs with local group Cp×CpC_p\times C_pCp​×Cp​ or Cp≀C2C_p \wr C_2Cp​≀C2​

Semiregular automorphisms of edge-transitive graphs

Asymptotic enumeration of vertex-transitive graphs of fixed valency

Cubic vertex-transitive graphs on up to 1280 vertices

On intransitive graph-restrictive permutation groups

On the order of arc-stabilisers in arc-transitive graphs with prescribed local group

Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph

On graph-restrictive permutation groups

Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs

Tetravalent arc-transitive graphs with unbounded vertex-stabilisers

See the researcher in context

Building this map preview

Abelian Varieties with $p$ -rank Zero

Distinguishing numbers of finite $4$ -valent vertex-transitive graphs

Three local actions in $6$ -valent arc-transitive graphs

Cubic arc-transitive $k$ -circulants

On $2$ -arc-transitive graphs of order $kp^n$

On the order of vertex-stabilisers in vertex-transitive graphs with local group $C_p\times C_p$ or $C_p \wr C_2$