The distortion dimension of $$\mathbb $$-rank 1 lattices

Let \(X=G/K\) be a symmetric space of noncompact type and rank \(k\ge 2\). We prove that horospheres in X are Lipschitz \((k-2)\)-connected if their centers are not contained in a proper join factor of the spherical building of X at infinity. As a consequence, the distortion dimension of an irreducible \(\mathbb {Q}\)-rank-1 lattice \(\Gamma \) in a linear, semisimple Lie group G of \(\mathbb R\)-rank k is \(k-1\). That is, given \(m< k-1\), a Lipschitz m-sphere S in (a polyhedral complex quasi-isometric to) \(\Gamma \), and a \((m+1)\)-ball B in X (or G) filling S, there is a \((m+1)\)-ball \(B'\) in \(\Gamma \) filling S such that \({{\mathrm{vol}}}B'\sim {{\mathrm{vol}}}B\). In particular, such arithmetic lattices satisfy Euclidean isoperimetric inequalities up to dimension \(k-1\).     

On the sumsets of exceptional units in $$\mathbb {Z}_n$$

Let R be a commutative ring with \(1\in R\) and \(R^{*}\) be the multiplicative group of its units. In 1969, Nagell introduced the concept of an exceptional unit, namely a unit u such that \(1-u\) is also a unit. Let \({\mathbb {Z}}_n\) be the ring of residue classes modulo n. In this paper, given an integer \(k\ge 2\), we obtain an exact formula for the number of ways to represent each element of \( \mathbb {Z}_n\) as the sum of k exceptional units. This generalizes a recent result of J. W. Sander for the case \(k=2\).     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

Monochromatic Sinks in <Emphasis Type="Italic">k</Emphasis>-Arc Colored Tournaments

Let T be a tournament on n vertices whose arcs are colored with k colors. A 3-cycle whose arcs are colored with three distinct colors is called a rainbow triangle. A rainbow triangle dominated by any nonempty set of vertices is called a dominated rainbow triangle. We prove that when \(n\ge 5\), if T does not contain a dominated rainbow triangle and all 4- and 5-cycles of T are near-monochromatic, then T has a monochromatic sink. We also prove that when \(n\ge 4\), if T does not contain a dominated rainbow triangle and all 4-cycles are monochromatic, then T has a monochromatic sink. A semi-cycle is a digraph C that either is a cycle or contains an arc xy such that \(C-xy+yx\) is a cycle. We prove that if \(n\ge 4\) and all 4-semi-cycles of T are near-monochromatic, then T has a monochromatic sink. We also show if \(n\ge 5\) and all 5-semi-cycles of T are near-monochromatic, then T has a monochromatic sink.     

On the minimum-cost $$\lambda $$-edge-connected k-subgraph problem

In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost \(\lambda \)-edge-connected k-subgraph problem, or the \((k,\lambda )\)-subgraph problem, based on its graph properties. Special cases of this problem include the well-known k-minimum spanning tree problem (if \(\lambda =1\)), \(\lambda \)-edge-connected spanning subgraph problem (if \(k=|V|\)) and k-clique problem (if \(\lambda = k-1\) and there are exact k vertices in the subgraph). As a generalization of k-minimum spanning tree and a case of the \((k,\lambda )\)-subgraph problem, the (k, 2)-subgraph problem is studied, and some special graph properties are proved to find stronger and more compact IP formulations. Additionally, we study the valid inequalities for these IP formulations. Numerical experiments are performed to compare proposed IP formulations and inequalities.     

Cliques in $$C_4$$-free graphs of large minimum degree

A graph G is called \(C_4\)-free if it does not contain the cycle \(C_4\) as an induced subgraph. Hubenko, Solymosi and the first author proved (answering a question of Erd?s) a peculiar property of \(C_4\)-free graphs: \(C_4\)-free graphs with n vertices and average degree at least cn contain a complete subgraph (clique) of size at least \(c'n\) (with \(c'= 0.1c^2\)). We prove here better bounds \(\big ({c^2n\over 2+c}\) in general and \((c-1/3)n\) when \( c \le 0.733\big )\) from the stronger assumption that the \(C_4\)-free graphs have minimum degree at least cn. Our main result is a theorem for regular graphs, conjectured in the paper mentioned above: 2k-regular \(C_4\)-free graphs on \(4k+1\) vertices contain a clique of size \(k+1\). This is the best possible as shown by the kth power of the cycle \(C_{4k+1}\).     

On the eigenvalues and spectral radius of starlike trees

Let \(k\ge 1\) and \(n_1,\ldots ,n_k\ge 1\) be some integers. Let \(S(n_1,\ldots ,n_k)\) be a tree T such that T has a vertex v of degree k and \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1},\ldots ,P_{n_k}\), that is \(T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}\) so that every neighbor of v in T has degree one or two. The tree \(S(n_1,\ldots ,n_k)\) is called starlike tree, a tree with exactly one vertex of degree greater than two, if \(k\ge 3\). In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if \(k\ge 4\) and \(n_1,\ldots ,n_k\ge 2\), then \(\frac{k-1}{\sqrt{k-2}}<\lambda _1(S(n_1,\ldots ,n_k))<\frac{k}{\sqrt{k-1}}\), where \(\lambda _1(T)\) is the largest eigenvalue of T. Finally we characterize all starlike trees that all of whose eigenvalues are in the interval \((-2,2)\).     

Connections on the Total Space of a Holomorphic Lie Algebroid

The main purpose of the paper is the study of the total space of a holomorphic Lie algebroid E. The paper is structured in three parts. In the first section, we briefly introduce basic notions on holomorphic Lie algebroids. The local expressions are written and the complexified holomorphic bundle is introduced. The second section presents two approaches on the study of the geometry of the complex manifold E. The first part contains the study of the tangent bundle \(T_{\mathbb {C}}E=T'E\oplus T''E\) and its link, via the tangent anchor map, with the complexified tangent bundle \(T_{\mathbb {C}}(T'M)=T'(T'M)\oplus T''(T'M)\). A holomorphic Lie algebroid structure is emphasized on \(T'E\). A special study is made for integral curves of a spray on \(T'E\). Theorem 2.8 gives the coefficients of a spray, called canonical, obtained from a complex Lagrangian on \(T'E\). In the second part of section two, we study the holomorphic prolongation \(\mathcal {T}'E\) of the Lie algebroid E. In the third section, we study how a complex Lagrange (Finsler) structure on \(T'M\) induces a Lagrangian structure on E. Three particular cases are analysed by the rank of the anchor map, the dimensions of manifold M, and those of the fibres. We obtain the correspondent on E of the Chern–Lagrange nonlinear connection from \(T'M\).     

The Terwilliger algebra of the incidence graph of the Hamming graph

Let \(\varGamma \) be a distance-semiregular graph on Y, and let \(D^Y\) be the diameter of \(\varGamma \) on Y. Let \(\varDelta \) be the halved graph of \(\varGamma \) on Y. Fix \(x \in Y\). Let T and \(T'\) be the Terwilliger algebras of \(\varGamma \) and \(\varDelta \) with respect to x, respectively. Assume, for an integer i with \(1 \le 2i \le D^Y\) and for \(y,z \in \varGamma _{2i}(x)\) with \(\partial _{\varGamma }(y,z)=2\), the numbers \(|\varGamma _{2i-1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) and \(|\varGamma _{2i+1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) depend only on i and do not depend on the choice of y, z. The first goal in this paper is to show the relations between T-modules of \(\varGamma \) and \(T'\)-modules of \(\varDelta \). Assume \(\varGamma \) is the incidence graph of the Hamming graph H(D, n) on the vertex set Y and the set \({\mathcal {C}}\) of all maximal cliques. Then, \(\varGamma \) satisfies above assumption and \(\varDelta \) is isomorphic to H(D, n). The second goal is to determine the irreducible T-modules of \(\varGamma \). For each irreducible T-module W, we give a basis for W the action of the adjacency matrix on this basis and we calculate the multiplicity of W.     

Subgroups of cyclic groups and values of the Riemann zeta function

Let k be a positive integer, x a large real number, and let \(C_n\) be the cyclic group of order n. For \(k\le n\le x\) we determine the mean average order of the subgroups of \(C_n\) generated by k distinct elements and we give asymptotic results of related averaging functions of the orders of subgroups of cyclic groups. The average order is expressed in terms of Jordan’s totient functions and Stirling numbers of the second kind. We have the following consequence. Let k and x be as above. For \(k\le n\le x\), the mean average proportion of \(C_n\) generated by k distinct elements approaches \(\zeta (k+2)/\zeta (k+1)\) as x grows, where \(\zeta (s)\) is the Riemann zeta function.     

Homotopy type of neighborhood complexes of Kneser graphs, $$\varvec{KG_{2,k}}$$

Schrijver (Nieuw Archief voor Wiskunde, 26(3) (1978) 454–461) identified a family of vertex critical subgraphs of the Kneser graphs called the stable Kneser graphs \(SG_{n,k}\). Björner and de Longueville (Combinatorica 23(1) (2003) 23–34) proved that the neighborhood complex of the stable Kneser graph \(SG_{n,k}\) is homotopy equivalent to a k-sphere. In this article, we prove that the homotopy type of the neighborhood complex of the Kneser graph \(KG_{2,k}\) is a wedge of \((k+4)(k+1)+1\) spheres of dimension k. We construct a maximal subgraph \(S_{2,k}\) of \(KG_{2,k}\), whose neighborhood complex is homotopy equivalent to the neighborhood complex of \(SG_{2,k}\). Further, we prove that the neighborhood complex of \(S_{2,k}\) deformation retracts onto the neighborhood complex of \(SG_{2,k}\).     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

The Gray image of constacyclic codes over the finite chain ring $$F_{p^m}[u]/\langle u^k\rangle $$

Let \(\mathbb {F}_{p^m}\) be a finite field of cardinality \(p^m\), where p is a prime, and k, N be any positive integers. We denote \(R_k=F_{p^m}[u]/\langle u^k\rangle =F_{p^m}+uF_{p^m}+\cdots +u^{k-1}F_{p^m}\) (\(u^k=0\)) and \(\lambda =a_0+a_1u+\cdots +a_{k-1}u^{k-1}\) where \(a_0, a_1,\ldots , a_{k-1}\in F_{p^m}\) satisfying \(a_0\ne 0\) and \(a_1=1\). Let r be a positive integer satisfying \(p^{r-1}+1\le k\le p^r\). First we define a Gray map from \(R_k\) to \(F_{p^m}^{p^r}\), then prove that the Gray image of any linear \(\lambda \)-constacyclic code over \(R_k\) of length N is a distance preserving linear \(a_0^{p^r}\)-constacyclic code over \(F_{p^m}\) of length \(p^rN\). Furthermore, the generator polynomials for each linear \(\lambda \)-constacyclic code over \(R_k\) of length N and its Gray image are given respectively. Finally, some optimal constacyclic codes over \(F_{3}\) and \(F_{5}\) are constructed.     

Newly appointed editors

Let k be a field and \(k(x_0,\ldots ,x_{p-1})\) be the rational function field of p variables over k where p is a prime number. Suppose that \(G=\langle \sigma \rangle \simeq C_p\) acts on \(k(x_0,\ldots ,x_{p-1})\) by k-automorphisms defined as \(\sigma :x_0\mapsto x_1\mapsto \cdots \mapsto x_{p-1}\mapsto x_0\). Denote by P the set of all prime numbers and define \(P_0=\{p\in P:\mathbb {Q}(\zeta _{p-1})\) is of class number one\(\}\) where \(\zeta _n\) a primitive n-th root of unity in \(\mathbb {C}\) for a positive integer n; \(P_0\) is a finite set by Masley and Montgomery (J Reine Angew Math 286/287:248–256, 1976). Theorem. Let k be an algebraic number field and \(P_k=\{p\in P: p\) is ramified in \(k\}\). Then \(k(x_0,\ldots ,x_{p-1})^G\) is not stably rational over k for all \(p\in P\backslash (P_0\cup P_k)\).     

Another proof of Grothendieck’s theorem on the splitting of vector bundles on the projective line

This note contains another proof of Grothendieck‘s theorem on the splitting of vector bundles on the projective line over a field k. Actually the proof is formulated entirely in the classical terms of a lattice \(\Lambda \cong k[T]^d\), discretely embedded into the vector space \(V \cong K_\infty ^d\), where \(K_\infty \cong k((1/T))\) is the completion of the field of rational functions k(T) at the place \(\infty \) with the usual valuation.     

Distance Magic Labeling in Complete 4-partite Graphs

Let G be a complete k-partite simple undirected graph with parts of sizes \(p_1\le p_2\cdots \le p_k\). Let \(P_j=\sum _{i=1}^jp_i\) for \(j=1,\ldots ,k\). It is conjectured that G has distance magic labeling if and only if \(\sum _{i=1}^{P_j} (n-i+1)\ge j{{n+1}\atopwithdelims (){2}}/k\) for all \(j=1,\ldots ,k\). The conjecture is proved for \(k=4\), extending earlier results for \(k=2,3\).     

Sharpening an Ore-type version of the Corrádi–Hajnal theorem

Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all \(k\ge 1\) and \(n\ge 3k\), every (simple) graph G on n vertices with minimum degree \(\delta (G)\ge 2k\) contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: For all \(k\ge 1\) and \(n\ge 3k\), every graph G on n vertices contains k disjoint cycles, provided that \(d(x)+d(y)\ge 4k-1\) for all distinct nonadjacent vertices x, y. Very recently, it was refined for \(k\ge 3\) and \(n\ge 3k+1\): If G is a graph on n vertices such that \(d(x)+d(y)\ge 4k-3\) for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number \(\alpha (G)\le n-2k\) and G is not one of two small exceptions in the case \(k=3\). But the most difficult case, \(n=3k\), was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.     

$${\varvec{}}$$-Jorda homomorphisms ad pseudo $${\varvec{}}$$-Jorda homomorphisms o Baach algebras

Let \(n\in \mathbb {N}\), A and B be Banach algebras and let B be a right A-module. We say that a linear mapping \(\varphi :A\longrightarrow B\) is a pseudo n-Jordan homomorphism if there exists an element \(w\in A\) such that \(\varphi (a^nw)=\varphi (a)^n\cdot w\), for every \(a\in A\) and \(n\ge \) 2. In this paper, among other things, we show that under some conditions if a linear mapping \(\varphi \) is a (pseudo) n-Jordan homomorphism, then it is a (pseudo) \((n + 1)\)-Jordan homomorphism. Additionally, we investigate automatic continuity of surjective pseudo n-Jordan homomorphisms under some conditions.     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

Largest independent sets of certain regular subgraphs of the derangement graph

The derangement graph is the Cayley graph on the symmetric group \(\mathcal {S}_{n}\) whose generating set \(D_{n}\) is the set of permutations on \([n]=\{1, \ldots , n\}\) without any 1-cycle. For any fixed positive integer \(k \le n\), the Cayley graph generated by the subset of \(D_{n}\) consisting of permutations without any i-cycles for all \(1 \le i \le k\) is a regular subgraph of the derangement graph. In this paper, we determine the smallest eigenvalue of these subgraphs and show that the set of all the largest independent sets in these subgraphs is equal to the set of all the largest independent sets in the derangement graph, provided n is sufficiently large in terms of k.