On the fastest moving off from a vertex in directed regular graphs

Let Γ be a directed regular locally finite graph, and let $\bar \Gamma $ be the undirected graph obtained by forgetting the orientation of Γ. Let x be a vertex of Γ and let n be a nonnegative integer. We study the length of the shortest directed path in Γ starting at x and ending outside of the ball of radius n centered at x in $\bar \Gamma $ .     

Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

Let Γ=(X,R) be a distance-regular graph of diameter d. A parallelogram of length i is a 4-tuple xyzw consisting of vertices of Γ such that ?(x,y)=?(z,w)=1, ?(x,z)=i, and ?(x,w)=?(y,w)=?(y,z)=i?1. A subset Y of X is said to be a completely regular code if the numbers

$\pi_{i,j}=|\Gamma_{j}(x)\cap Y|\quad (i,j\in \{0,1,\ldots,d\})$

depend only on i=?(x,Y) and j. A subset Y of X is said to be strongly closed if

$\{x\mid \partial(u,x)\leq \partial(u,v),\partial(v,x)=1\}\subset Y,\mbox{ whenever }u,v\in Y.$

Hamming graphs and dual polar graphs have strongly closed completely regular codes. In this paper, we study parallelogram-free distance-regular graphs having strongly closed completely regular codes. Let Γ be a parallelogram-free distance-regular graph of diameter d≥4 such that every strongly closed subgraph of diameter two is completely regular. We show that Γ has a strongly closed subgraph of diameter d?1 isomorphic to a Hamming graph or a dual polar graph. Moreover if the covering radius of the strongly closed subgraph of diameter two is d?2, Γ itself is isomorphic to a Hamming graph or a dual polar graph. We also give an algebraic characterization of the case when the covering radius is d?2.

     

Power Majorization and Majorization of Sequences

Let \(\bar x\) , \(\bar y\ \in\ R_n\) be vectors which satisfy x₁ ≥ x₂ ≥ … ≥ x_n and y₁ ≥ y₂ >- … ≥ y_n and Σx_i = Σy_i. We say that \(\bar x\) is power majorized by \(\bar y\) if Σx_i ^p ≤ Σy_i ^p for all real p ? [0, 1] and Σx_i ^p ≥ Σy_i ^p for p ∈ [0, 1]. In this paper we give a classification of functions ? (which includes all possible positive polynomials) for which \(\bar\phi(\bar x) \leq \bar\phi(\bar y)\) (see definition below) when \(\bar x\) is power majorized \(\bar y\) . We also answer a question posed by Clausing by showing that there are vectors \(\bar x\) , \(\bar y\ \in\ R^n\) of any dimension n ≥ 4 for which there is a convex function ? such that \(\bar x\) is power majorized by \(\bar y\) and \(\bar\phi(\bar x)\ >\ \bar\phi(\bar y)\) .     

Riesz Means on Graphs and Discrete Groups

Suppose that Γ is a weighted graph or a discrete group. Let $m_{\alpha,R}(\lambda )=\big(1-\big|\frac{\lambda}{R}\big|\big)_{+}^{\alpha}$ be the Riesz means and let Δ be the discrete Laplacian on Γ. We prove that if D is the homogeneous dimension of Γ then the operator m _α,R (Δ) is bounded on L ^p , provided that $\alpha>D|\frac{1}{p}-\frac{1}{2}|$ .     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

Score sequences in oriented graphs

An oriented graph is a digraph with no symmetric pairs of directed arcs and without loops. The score of a vertexv _i in an oriented graph D is $a_{v_i } $ (or simply a_i) $d_{v_i }^ - $ are the outdegree and indegree, respectively, ofv _i and n is the number of vertices in D. In this paper, we give a new proof of Avery’s theorem and obtain some stronger inequalities for scores in oriented graphs. We also characterize strongly transitive oriented graphs.     

Cohomology of discontinuous groups

Prasad (1979) proved that the set of all equivalence classes of representationsp of a Fuchsian group Γ whose restrictions to the cyclic subgroups Γ _i -(c _i ) corresponding to the parabolic and elliptic elements of Γ occurring in the structure of Γ, are given, is a complex analytic manifold. In the process the author has proved thatH ¹(X,A)≈P ¹(Γ,ρ) and with suitable notation. This paper gives the corresponding results to the two above mentioned results, when in place of Γ we consider any discontinuous group of Poincare isometries Δ, and when similar assumptions are made.     

Tangential polynomials and matrix KdV elliptic solitons

Let (X, q) be an elliptic curve marked at the origin. Starting from any cover π: Γ → X of an elliptic curve X marked at d points {π _i } of the fiber π ^?1(q) and satisfying a particular criterion, Krichever constructed a family of d × d matrix KP solitons, that is, matrix solutions, doubly periodic in x, of the KP equation. Moreover, if Γ has a meromorphic function f: Γ → P¹ with a double pole at each p _i , then these solutions are doubly periodic solutions of the matrix KdV equation U _t = 1/4(3UU _x + 3U _x U + U _xxx ). In this article, we restrict ourselves to the case in which there exists a meromorphic function with a unique double pole at each of the d points {p _i }; i.e. Γ is hyperelliptic and each pi is a Weierstrass point of Γ. More precisely, our purpose is threefold: (1) present simple polynomial equations defining spectral curves of matrix KP elliptic solitons; (2) construct the corresponding polynomials via the vector Baker–Akhiezer function of X; (3) find arbitrarily high genus spectral curves of matrix KdV elliptic solitons.     

New results related to a conjecture of Moore

Let Γ be a group, Γ′ be a subgroup of Γ of finite index, and R be a ring with identity. Assume that M is an RΓ-module whose restriction to RΓ′ is projective. Moore’s conjecture: Assume that, for all ${x \in (\Gamma-\Gamma^{\prime})}$ , either there is an integer n such that ${1 \neq x^{n} \in \Gamma^{\prime}}$ or x has finite order and is invertible in R. Then M is also projective over RΓ. In this paper, we consider an analogue of this conjecture for injective modules. It turns out that the validity of the conjecture for injective modules implies the validity of it on projective and flat modules. It is also shown that the conjecture for injective modules is true whenever Γ belongs to Kropholler’s hierarchy ${{\bf LH}\mathfrak{F}}$ . In addition, assume that M is an RΓ-module whose restriction to RΓ′ is Gorenstein projective (resp. injective), it is proved that M is Gorenstein projective (resp. injective) over RΓ whenever Γ′ is a subgroup of Γ of finite index.     

On Bipartite Distance-Regular Graphs with Intersection Numbers c i = (q i ? 1)/(q ? 1)

Let q denote an integer at least two. Let ?? denote a bipartite distance-regular graph with diameter D ?? 3 and intersection numbers c _i = (q ⁱ ? 1)/(q ? 1), 1 ?? i ?? D. Let X denote the vertex set of ?? and let ${V = \mathbb{C}^X}$ denote the vector space over ${\mathbb{C}}$ consisting of column vectors whose coordinates are indexed by X and whose entries are in ${\mathbb{C}}$ . For ${z \in X}$ , let ${{\hat z}}$ denote the vector in V with a 1 in the z-coordinate and 0 in all other coordinates. Fix ${x, y \in X}$ such that ?(x, y) = 2, where ? denotes the path-length distance function. For 0 ?? i, j ?? D define ${w_{ij} = \sum {\hat z}}$ , where the sum is over all ${z \in X}$ such that ?(x, z) = i and ?(y, z) = j. We define W?=?span{w _ij | 0 ?? i, j ?? D}. In this paper we consider the space ${MW={\rm span} \{mw \mid m \in M, w \in W\}}$ , where M is the Bose?CMesner algebra of ??. We observe that MW is the minimal A-invariant subspace of V which contains W, where A is the adjacency matrix of ??. We give a basis for MW that is orthogonal with respect to the Hermitean dot product. We compute the square-norm of each basis vector. We compute the action of A on the basis. For the case in which ?? is the dual polar graph D _D (q) we show that the basis consists of the characteristic vectors of the orbits of the stabilizer of x and y in the automorphism group of ??.     

La monotonia di rappresentazioni del gruppo libero

Let Γ be a free nonabelian group on finitely many generators. Let Ω be the boundary of Γ, letC(Ω) be theC ^*-algebra of continuous functions on Ω, and let λ be the natural action of Γ onC(Ω). Aboundary representation is a representation of the crossed productC ^*-algebra Γ×_λ C(Ω). Given a unitary representation π of Γ onH, aboundary realization of π is an isometric Γ-inclusion ofH into the space of a boundary representation whose image is cyclic for that boundary representation. If the Γ-inclusion is bijective, we call, the realizationperfect. We prove below that if π admits an imperfect boundary realization, then there exists a nonzero vectorv ₀∈H satisfying $$\sum\limits_{|x| = n} {|\left\langle {v,\pi (x)v_0 } \right\rangle |^2 \leqslant |v|^2 } for each v \in {\mathcal{H}} (GVB)$$ If π is irreducible and weakly contained in the regular representation, and if no suchv ₀ exists, it follows that π satisfiesmonotony: up to equivalence, there exists exactly one realization of π, and that realization is perfect.     

A Note on Comaximal Graph of Non-commutative Rings

Let R be a ring with unity. The graph Γ(R) is a graph with vertices as elements of R, where two distinct vertices a and b are adjacent if and only if Ra?+?Rb?=?R. Let Γ₂(R) be the subgraph of Γ(R) induced by the non-unit elements of R. Let R be a commutative ring with unity and let J(R) denote the Jacobson radical of R. If R is not a local ring, then it was proved that:

1. If $\Gamma_2(R)\backslash J(R)$ is a complete n-partite graph, then n?=?2.
2. If there exists a vertex of $\Gamma_2(R)\backslash J(R)$ which is adjacent to every vertex, then R????₂×F, where F is a field.

In this note we generalize the above results to non-commutative rings and characterize all non-local ring R (not necessarily commutative) whose $\Gamma_2(R)\backslash J(R)$ is a complete n-partite graph.     

A constructive description of Hölder classes on closed Jordan curves

Let Γ be a closed, Jordan, rectifiable curve, whose are length is commensurable with its subtending chord, leta ε int Γ, and let R_n(a) be the set of rational functions of degree ≤n, having a pole perhaps only at the pointa. Let Λ^α(Γ), 0 < α < 1, be the Hölder class on Γ. One constructs a system of weights γ_n(z) > 0 on Γ such that f∈Λ^α(Γ) if and only if for any nonnegative integer n there exists a function R_n, R_n ε R_n(a) such that ¦f(z) ? R_n(z)¦ ≤ c_f·γ_n(z), z ε Γ. It is proved that the weights γ_n cannot be expressed simply in terms of ρ ₁ ⁺ /n^(z) and ρ ₁ ^- /n^(z), the distances to the level lines of the moduli of the conformal mappings of ext Γ and int Γ on \(\mathbb{C}\backslash \mathbb{D}\) .     

Distance-Regular Shilla Graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>2</Subscript> = <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript>

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ₁ equal to a₃. For a Shilla graph, let us put a = a₃ and b = k/a. It is proved in this paper that a Shilla graph with b₂ = c₂ and noninteger eigenvalues has the following intersection array:

$$\left\{ {\frac{{{b^2}\left( {b - 1} \right)}}{2},\frac{{\left( {b - 1} \right)\left( {{b^2} - b + 2} \right)}}{2},\frac{{b\left( {b - 1} \right)}}{4};1,\frac{{b\left( {b - 1} \right)}}{4},\frac{{b{{\left( {b - 1} \right)}^2}}}{2}} \right\}$$

If Γ is a Q-polynomial Shilla graph with b₂ = c₂ and b = 2r, then the graph Γ has intersection array

$$\left\{ {2tr\left( {2r + 1} \right),\left( {2r + 1} \right)\left( {2rt + t + 1} \right),r\left( {r + t} \right);1,r\left( {r + t} \right),t\left( {4{r^2} - 1} \right)} \right\}$$

and, for any vertex u in Γ, the subgraph Γ₃(u) is an antipodal distance-regular graph with intersection array

$$\left\{ {t\left( {2r + 1} \right),\left( {2r - 1} \right)\left( {t + 1} \right),1;1,t + 1,t\left( {2r + 1} \right)} \right\}$$

The Shilla graphs with b₂ = c₂ and b = 4 are also classified in the paper.

     

An analogue of Artin’s conjecture for multiplicative subgroups of the rationals

Given ${\Gamma \subset \mathbb{Q}^*}$ a multiplicative subgroup and ${m \in \mathbb{N}^+}$ , assuming the Generalized Riemann Hypothesis, we determine an asymptotic formula for the number of primes p ≤ x for which ind _p Γ = m, where ind _p Γ = (p ? 1)/|Γ _p | and Γ _p is the reduction of Γ modulo p. This problem is a generalization of some earlier works by Cangelmi–Pappalardi, Lenstra, Moree, Murata, Wagstaff, and probably others. We prove, on GRH, that the primes with this property have a density and, in the case when Γ contains only positive numbers, we give an explicit expression for it in terms of an Euler product. We conclude with some numerical computations.     

Eulerian graphs and automorphisms of a maximal graph

Let R be a commutative ring with identity. Let Γ(R) denote the maximal graph corresponding to the non-unit elements of R, i.e., Γ(R) is a graph with vertices the non-unit elements of R, where two distinct vertices a and b are adjacent if and only if there is a maximal ideal of R containing both. In this paper, we have shown that, for any finite ring R which is not a field, Γ(R) is a Euler graph if and only if R has odd cardinality. Moreover, for any finite ring R ? R ₁×R ₂× · · · ×R _n, where the R _i is a local ring of cardinality p _i ^αi for all i, and the p _i’s are distinct primes, it is shown that Aut(Γ(R)) is isomorphic to a finite direct product of symmetric groups. We have also proved that clique(G(R)’) = χ(G(R)’) for any semi-local ring R, where G(R)’ denote the comaximal graph associated to R.     

An Erdös-Ko-Rado theorem for the subcubes of a cube

LetP be that partially ordered set whose elements are vectors x=(x ₁, ...,x _n ) withx _i ε {0, ...,k} (i=1, ...,n) and in which the order is given byx≦y iffx _i =y _i orx _i =0 for alli. LetN _i (P)={x εP : |{j:x _j ≠ 0}|=i}. A subsetF ofP is called an Erdös-Ko-Rado family, if for allx, y εF it holdsx ≮y, x ≯ y, and there exists az εN ₁(P) such thatz≦x andz≦y. Let ? be the set of all vectorsf=(f ₀, ...,f _n ) for which there is an Erdös-Ko-Rado familyF inP such that |N _i (P) ∩F|=f _i (i=0, ...,n) and let 〈?〉 be its convex closure in the (n+1)-dimensional Euclidean space. It is proved that fork≧2 (0, ..., 0) and \(\left( {0,...,0,\overbrace {i - component}^{\left( {\begin{array}{*{20}c} {n - 1} \\ {i - 1} \\ \end{array} } \right)}k^{i - 1} ,0,...,0} \right)\) (i=1, ...,n) are the vertices of 〈?〉.     

A Spanning Tree with High Degree Vertices

Let G be a connected graph, let ${X \subset V(G)}$ and let f be a mapping from X to {2, 3, . . .}. Kaneko and Yoshimoto (Inf Process Lett 73:163–165, 2000) conjectured that if |N _G (S) ? X| ≥ f (S) ? 2|S| + ω _G (S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ . In this paper, we show a result with a stronger assumption than this conjecture; if |N _G (S) ? X| ≥ f (S) ? 2|S| + α(S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ .     

Difference Sets in {\mathbb{Z}}_4^m and {\mathbb{F}}_2^{2m}

Let R=GR(4,m) be the Galois ring of cardinality 4^m and let T be the Teichmüller system of R. For every map λ of T into { -1,+1} and for every permutation Π of T, we define a map φ _λ ^Π of Rinto { -1,+1} as follows: if x∈R and if x=a+2b is the 2-adic representation of x with x∈T and b∈T, then φ _λ ^Π (x)=λ(a)+2Tr(Π(a)b), where Tr is the trace function of R . For i=1 or i=-1, define D _i as the set of x in R such thatφ _λ ^Π =i. We prove the following results: 1) D _i is a Hadamard difference set of (R,+). 2) If φ is the Gray map of R into ${\mathbb{F}}_2^{2m}$ , then (D _i) is a difference set of ${\mathbb{F}}_2^{2m}$ . 3) The set of D _i and the set of φ(D _i) obtained for all maps λ and Π, both are one-to-one image of the set of binary Maiorana-McFarland difference sets in a simple way. We also prove that special multiplicative subgroups of R are difference sets of kind D _i in the additive group of R. Examples are given by means of morphisms and norm in R.     

Estimates for interval probabilities of the sums of random variables with locally subexponential distributions

Let {_i} _i=1 be a sequence of independent identically distributed nonnegative random variables, S _n = ξ₁ + ? +ξ_n. Let Δ = (0, T] and x + Δ = (x, x + T]. We study the ratios of the probabilities P(S _n ε x + Δ)/P(ξ ₁ ε x + Δ) for all n and x. The estimates uniform in x for these ratios are known for the so-called Δ-subexponential distributions. Here we improve these estimates for two subclasses of Δ-subexponential distributions; one of them is a generalization of the well-known class LC to the case of the interval (0, T] with an arbitrary T ≤ ∞. Also, a characterization of the class LC is given.