Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Bipartiteness Constant and Expansion of Cayley Graphs
98
0
0.0
(
0
)
Added by
Peter Ralli
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1 = lambda_1(A)geq dots ge lambda_n ge -1$. It is a classical fact that $lambda_n = -1$ if and only if $G$ is bipartite. Our main result provides a quantitative separation of $lambda_n$ from $-1$ in the case of Cayley graphs, in terms of their expansion. Denoting $h_{out}$ by the (outer boundary) vertex expansion of $G$, we show that if $G$ is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size $d$) then $lambda_n ge -1 + ch_{out}^2/d^2,,$ for $c$ an absolute constant. We exhibit graphs for which this result is tight up to a factor depending on $d$. This improves upon a recent result by Biswas and Saha who showed $lambda_n ge -1 + h_{out}^4/(2^9d^8),.$ We also note that such a result could not be true for general non-bipartite graphs.
rate research
Read More
We show that any connected Cayley graph $Gamma$ on an Abelian group of order $2n$ and degree $tilde{Omega}(log n)$ has at most $2^{n+1}(1 + o(1))$ independent sets. This bound is tight up to to the $o(1)$ term when $Gamma$ is bipartite. Our proof is based on Sapozhenkos graph container method and uses the Pl{u}nnecke-Rusza-Petridis inequality from additive combinatorics.
In this paper we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible automorphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is complicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing separately the cases where the regular group $R$ has a nontrivial proper normal subgroup $N$ with the property that the automorphism group of the digraph fixes each $N$-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.
Let $G$ be a finitely generated group acting faithfully and properly discontinuously by homeomorphisms on a planar surface $X subseteq mathbb{S}^2$. We prove that $G$ admits such an action that is in addition co-compact, provided we can replace $X$ by another surface $Y subseteq mathbb{S}^2$. We also prove that if a group $H$ has a finitely generated Cayley (multi-)graph $C$ covariantly embeddable in $mathbb{S}^2$, then $C$ can be chosen so as to have no infinite path on the boundary of a face. The proofs of these facts are intertwined, and the classes of groups they define coincide. In the orientation-preserving case they are exactly the (isomorphism types of) finitely generated Kleinian function groups. We construct a finitely generated planar Cayley graph whose group is not in this class. In passing, we observe that the Freudenthal compactification of every planar surface is homeomorphic to the sphere.
A Cayley graph over a group G is said to be central if its connection set is a normal subset of G. It is proved that for any two central Cayley graphs over explicitly given almost simple groups of order n, the set of all isomorphisms from the first graph onto the second can be found in time poly(n).
We construct a polynomial-time algorithm that given a graph $X$ with $4p$ vertices ($p$ is prime), finds (if any) a Cayley representation of $X$ over the group $C_2times C_2times C_p$. This result, together with the known similar result for circulant graphs, shows that recognising and testing isomorphism of Cayley graphs over an abelian group of order $4p$ can be done in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
