Pentavalent symmetric graphs of order 2p3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.     

Edge-Colorings of 4-Regular Graphs with the Minimum Number of Palettes

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Wo?niak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs. In particular, we show that certain values of the palette index imply the existence of an even cycle decomposition of size 3 (a partition of the edge-set of a graph into 3 2-regular subgraphs whose connected components are cycles of even length). This result can be extended to 4d-regular graphs. Moreover, in studying the palette index of a 4-regular graph, the following problem arises: does there exist a 4-regular graph whose even cycle decompositions cannot have size smaller than 4?     

Quantum diffusion of the random Schrödinger evolution in the scaling limit

We consider random Schrödinger equations on R ^d for d???3 with a homogeneous Anderson–Poisson type random potential. Denote by λ the coupling constant and \(\psi_t\) the solution with initial data \(\psi_0\). The space and time variables scale as \(x\sim\lambda ^{{ - 2 - \varkappa/2}} {\text{ and }}t\sim\lambda ^{{ - 2 - \varkappa}} {\text{ with }}0 < \varkappa < \varkappa_{0} {\left( d \right)}\). We prove that, in the limit λ?→?0, the expectation of the Wigner distribution of \(\psi_t\) converges weakly to the solution of a heat equation in the space variable x for arbitrary L ² initial data.The proof is based on analyzing the phase cancellations of multiple scatterings on the random potential by expanding the propagator into a sum of Feynman graphs. In this paper we consider the non-recollision graphs and prove that the amplitude of the non-ladder diagrams is smaller than their “naive size” by an extra λ ^c factor per non-(anti)ladder vertex for some c?>?0. This is the first rigorous result showing that the improvement over the naive estimates on the Feynman graphs grows as a power of the small parameter with the exponent depending linearly on the number of vertices. This estimate allows us to prove the convergence of the perturbation series.     

Linear arboricity of regular digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.     

An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

Dimension and Matchings in Comparability and Incomparability Graphs

We develop some new inequalities for the dimension of a finite poset. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d=3, then there is a matching of size d in the comparability graph of P. There is no analogue of this result for cover graphs, as we show that there is a poset P of dimension d for which the maximum matching in the cover graph of P has size \(O(\log d)\). On the other hand, there is a dual result in which the role of chains and antichains is reversed, as we show that there is also a matching of size d in the incomparability graph of P. The proof of the result for comparability graphs has elements in common with Perles’ proof of Dilworth’s theorem. Either result has the following theorem of Hiraguchi as an immediate corollary: \(\dim (P)\le |P|/2\) when |P|=4.     

Maximum independent sets on random regular graphs

We determine the asymptotics of the independence number of the random d-regular graph for all \({d\geq d_0}\). It is highly concentrated, with constant-order fluctuations around \({n\alpha_*-c_*\log n}\) for explicit constants \({\alpha_*(d)}\) and \({c_*(d)}\). Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.     

On the Hausdorff Dimension of Continuous Functions Belonging to Hölder and Besov Spaces on Fractal <Emphasis Type="Italic">d</Emphasis>-Sets

The Hausdorff dimension of the graphs of the functions in Hölder and Besov spaces (in this case with integrability p≥1) on fractal d-sets is studied. Denoting by s∈(0,1] the smoothness parameter, the sharp upper bound min{d+1?s,d/s} is obtained. In particular, when passing from d≥s to d<s there is a change of behaviour from d+1?s to d/s which implies that even highly nonsmooth functions defined on cubes in ? ⁿ have not so rough graphs when restricted to, say, rarefied fractals.     

Diversity vectors of balls in graphs and estimates of the components of the vectors

The diversity vectors of balls are considered (the ith component of a vector of this kind is equal to the number of different balls of radius i) for the usual connected graphs and the properties of the components of the vectors are studied. The sharp upper and lower estimates are obtained for the number of different balls of a given radius in the n-vertex graphs (trees) and n-vertex trees (graphs with n ? 2d) of diameter d. It is shown that the estimates are precise in every graph regardless of the radius of balls. It is proven a necessary and sufficient condition is given for the existence of an n-vertex graph of diameter d with local (complete) diversity of balls.     

On dihedrants admitting arc-regular group actions

We consider Cayley graphs Γ over dihedral groups, dihedrants for short, which admit an automorphism group G acting regularly on the arc set of Γ. We prove that, if D _2n ≤G≤Aut(Γ) is a regular dihedral subgroup of G of order 2n such that any of its index 2 cyclic subgroups is core-free in G, then Γ belongs to the family of graphs of the form \((K_{n_{1}}\otimes\cdots\otimes K_{n_{\ell}})[K_{m}^{\mathrm{c}}]\), where 2n=n ₁???n _? m, and the numbers n _i are pairwise coprime. Applications to 1-regular dihedrants and Cayley maps on dihedral groups are also given.     

The spectral excess theorem for distance-regular graphs having distance-<Emphasis Type="Italic">d</Emphasis> graph with fewer distinct eigenvalues

Let \(\Gamma \) be a distance-regular graph with diameter d and Kneser graph \(K=\Gamma _d\), the distance-d graph of \(\Gamma \). We say that \(\Gamma \) is partially antipodal when K has fewer distinct eigenvalues than \(\Gamma \). In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with \(d+1\) distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.     

Strictly Deza line graphs

For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs.     

Quantum quaternion spheres

For the quantum symplectic group SP _q (2n), we describe the C ^?-algebra of continuous functions on the quotient space S P _q (2n)/S P _q (2n?2) as an universal C ^?-algebra given by a finite set of generators and relations. The proof involves a careful analysis of the relations, and use of the branching rules for representations of the symplectic group due to Zhelobenko. We then exhibit a set of generators of the K-groups of this C ^?-algebra in terms of generators of the C ^?-algebra.     

Finite edge-transitive oriented graphs of valency four with cyclic normal quotients

We study finite four-valent graphs \(\Gamma \) admitting an edge-transitive group G of automorphisms such that G determines and preserves an edge-orientation on \(\Gamma \), and such that at least one G-normal quotient is a cycle (a quotient modulo the orbits of a normal subgroup of G). We show, on the one hand, that the number of distinct cyclic G-normal quotients can be unboundedly large. On the other hand, existence of independent cyclic G-normal quotients (that is, they are not extendable to a common cyclic G-normal quotient) places severe restrictions on the graph \(\Gamma \) and we classify all examples. We show there are five infinite families of such pairs \((\Gamma ,G)\) and in particular that all such graphs have at least one normal quotient which is an unoriented cycle. We compare this new approach with existing treatments for the sub-class of weak metacirculant graphs with these properties, finding that only two infinite families of examples occur in common from both analyses. Several open problems are posed.     

Asymptotic approximation for the number of <Emphasis Type="Italic">n</Emphasis>-vertex graphs of given diameter

We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Variations of Landau’s theorem for p-regular and p-singular conjugacy classes

The well-known Landau’s theorem states that, for any positive integer k, there are finitely many isomorphism classes of finite groups with exactly k (conjugacy) classes. We study variations of this theorem for p-regular classes as well as p-singular classes. We prove several results showing that the structure of a finite group is strongly restricted by the number of p-regular classes or the number of p-singular classes of the group. In particular, if G is a finite group with O_p(G) = 1 then |G/F(G)|_p' is bounded in terms of the number of p-regular classes of G. However, it is not possible to prove that there are finitely many groups with no nontrivial normal p-subgroup and kp-regular classes without solving some extremely difficult number-theoretic problems (for instance, we would need to show that the number of Fermat primes is finite).     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

On the Probabilistic Nature of Quantum Mechanics and the Notion of Closed Systems

The notion of “closed systems” in Quantum Mechanics is discussed. For this purpose, we study two models of a quantum mechanical system P spatially far separated from the “rest of the universe” Q. Under reasonable assumptions on the interaction between P and Q, we show that the system P behaves as a closed system if the initial state of P ∨ Q belongs to a large class of states, including ones exhibiting entanglement between P and Q. We use our results to illustrate the non-deterministic nature of quantum mechanics. Studying a specific example, we show that assigning an initial state and a unitary time evolution to a quantum system is generally not sufficient to predict the results of a measurement with certainty.