Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA combinatorial approach to counting primitive periodic and primitive pseudo orbits on circulant graphs
253
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We count the numbers of primitive periodic orbits on families of 4-regular directed circulant graphs with $n$ vertices. The relevant counting techniques are then extended to count the numbers of primitive pseudo orbits (sets of distinct primitive periodic orbits) up to length $n$ that lack self-intersections, or that never intersect at more than a single vertex at a time repeated exactly twice for each self-intersection (2-encounters of length zero), for two particular families of graphs. We then regard these two families of graphs as families of quantum graphs and use the counting results to compute the variance of the coefficients of the quantum graphs characteristic polynomial.
rate research
Read More
A graph is edge-primitive if its automorphism group acts primitively on the edge set. In this short paper, we prove that a finite 2-arc-transitive edge-primitive graph has almost simple automorphism group if it is neither a cycle nor a complete bipartite graph. We also present two examples of such graphs, which are 3-arc-transitive and have faithful vertex-stabilizers.
This paper begins the classification of all edge-primitive 3-arc-transitive graphs by classifying all such graphs where the automorphism group is an almost simple group with socle an alternating or sporadic group, and all such graphs where the automorphism group is an almost simple classical group with a vertex-stabiliser acting faithfully on the set of neighbours.
A graph is edge-primitive if its automorphism group acts primitively on the edge set, and 2-arc-transitive if its automorphism group acts transitively on the set of 2-arcs. In this paper, we present a classification for those edge-primitive graphs which are 2-arc-transitive and have soluble edge-stabilizers.
We derive combinatorial necessary conditions for discrete-time quantum walks defined by regular mixed graphs to be periodic. If the quantum walk is periodic, all the eigenvalues of the time evolution matrices must be algebraic integers. Focusing on this, we explore which ring the coefficients of the characteristic polynomials should belong to. On the other hand, the coefficients of the characteristic polynomials of $eta$-Hermitian adjacency matrices have combinatorial implications. From these, we can find combinatorial implications in the coefficients of the characteristic polynomials of the time evolution matrices, and thus derive combinatorial necessary conditions for mixed graphs to be periodic. For example, if a $k$-regular mixed graph with $n$ vertices is periodic, then $2n/k$ must be an integer. As an application of this work, we determine periodicity of mixed complete graphs and mixed graphs with a prime number of vertices.
We establish the existence of free energy limits for several combinatorial models on Erd{o}s-R{e}nyi graph $mathbb {G}(N,lfloor cNrfloor)$ and random $r$-regular graph $mathbb {G}(N,r)$. For a variety of models, including independent sets, MAX-CUT, coloring and K-SAT, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. This resolves an open problem which was proposed by Aldous (Some open problems) as one of his six favorite open problems. It was also mentioned as an open problem in several other places: Conjecture 2.20 in Wormald [In Surveys in Combinatorics, 1999 (Canterbury) (1999) 239-298 Cambridge Univ. Press]; Bollob{a}s and Riordan [Random Structures Algorithms 39 (2011) 1-38]; Janson and Thomason [Combin. Probab. Comput. 17 (2008) 259-264] and Aldous and Steele [In Probability on Discrete Structures (2004) 1-72 Springer].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
