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\).     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

Most small $${\varvec{}}$$-grous have an automorhism of order 2

Let f(p, n) be the number of pairwise nonisomorphic p-groups of order \(p^n\), and let g(p, n) be the number of groups of order \(p^n\) whose automorphism group is a p-group. We prove that the limit, as p grows to infinity, of the ratio g(p, n) / f(p, n) equals 1/3 for \(n=6,7\).     

Optimal channel assignment and <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, 1)-labeling

The optimal channel assignment is an important optimization problem with applications in optical networks. This problem was formulated to the L(p, 1)-labeling of graphs by Griggs and Yeh (SIAM J Discrete Math 5:586–595, 1992). A k-L(p, 1)-labeling of a graph G is a function \(f:V(G)\rightarrow \{0,1,2,\ldots ,k\}\) such that \(|f(u)-f(v)|\ge p\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\ge 1\) if \(d(u,v)=2\), where d(u, v) is the distance between the two vertices u and v in the graph. Denote \(\lambda _{p,1}^l(G)= \min \{k \mid G\) has a list k-L(p, 1)-labeling\(\}\). In this paper we show upper bounds \(\lambda _{1,1}^l(G)\le \Delta +9\) and \(\lambda _{2,1}^l(G)\le \max \{\Delta +15,29\}\) for planar graphs G without 4- and 6-cycles, where \(\Delta \) is the maximum vertex degree of G. Our proofs are constructive, which can be turned to a labeling (channel assignment) method to reach the upper bounds.     

Uniform approximation of the heat kernel on a manifold

We approximate the heat kernel h(x, y, t) on a compact connected Riemannian manifold M without boundary uniformly in \((x,y,t)\in M\times M\times [a,b]\), \(a>0\), by n-fold integrals over \(M^n\) of the densities of Brownian bridges. Moreover, we provide an estimate for the uniform convergence rate. As an immediate corollary, we get a uniform approximation of solutions of the Cauchy problem for the heat equation on M.     

Hermitian rank distance codes

Let \(X=X(n,q)\) be the set of \(n\times n\) Hermitian matrices over \(\mathbb {F}_{q^2}\). It is well known that X gives rise to a metric translation association scheme whose classes are induced by the rank metric. We study d-codes in this scheme, namely subsets Y of X with the property that, for all distinct \(A,B\in Y\), the rank of \(A-B\) is at least d. We prove bounds on the size of a d-code and show that, under certain conditions, the inner distribution of a d-code is determined by its parameters. Except if n and d are both even and \(4\le d\le n-2\), constructions of d-codes are given, which are optimal among the d-codes that are subgroups of \((X,+)\). This work complements results previously obtained for several other types of matrices over finite fields.     

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))\).     

Coloring of the Square of Kneser Graph $$$$

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n elements set, with two vertices adjacent if they are disjoint. The square \(G^2\) of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in \(G^2\) if the distance between u and v in G is at most 2. Determining the chromatic number of the square of the Kneser graph K(n, k) is an interesting graph coloring problem, and is also related with intersecting family problem. The square of K(2k, k) is a perfect matching and the square of K(n, k) is the complete graph when \(n \ge 3k-1\). Hence coloring of the square of \(K(2k +1, k)\) has been studied as the first nontrivial case. In this paper, we focus on the question of determining \(\chi (K^2(2k+r,k))\) for \(r \ge 2\). Recently, Kim and Park (Discrete Math 315:69–74, 2014) showed that \(\chi (K^2(2k+1,k)) \le 2k+2\) if \( 2k +1 = 2^t -1\) for some positive integer t. In this paper, we generalize the result by showing that for any integer r with \(1 \le r \le k -2\),

1. (a)
   \(\chi (K^2 (2k+r, k)) \le (2k+r)^r\),   if   \(2k + r = 2^t\) for some integer t, and
    
2. (b)
   \(\chi (K^2 (2k+r, k)) \le (2k+r+1)^r\),   if  \(2k + r = 2^t-1\) for some integer t.
    

On the other hand, it was shown in Kim and Park (Discrete Math 315:69–74, 2014) that \(\chi (K^2 (2k+r, k)) \le (r+2)(3k + \frac{3r+3}{2})^r\) for \(2 \le r \le k-2\). We improve these bounds by showing that for any integer r with \(2 \le r \le k -2\), we have \(\chi (K^2 (2k+r, k)) \le 2 \left( \frac{9}{4}k + \frac{9(r+3)}{8} \right) ^r\). Our approach is also related with injective coloring and coloring of Johnson graph.

     

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset P, denoted \(\dim (P)\), is the least positive integer d for which P is the intersection of d linear extensions of P. The maximum dimension of a poset P with \(|P|\le 2n+1\) is n, provided \(n\ge 2\), and this inequality is tight when P contains the standard example \(S_n\). However, there are posets with large dimension that do not contain the standard example \(S_2\). Moreover, for each fixed \(d\ge 2\), if P is a poset with \(|P|\le 2n+1\) and P does not contain the standard example \(S_d\), then \(\dim (P)=o(n)\). Also, for large n, there is a poset P with \(|P|=2n\) and \(\dim (P)\ge (1-o(1))n\) such that the largest d so that P contains the standard example \(S_d\) is o(n). In this paper, we will show that for every integer \(c\ge 1\), there is an integer \(f(c)=O(c^2)\) so that for large enough n, if P is a poset with \(|P|\le 2n+1\) and \(\dim (P)\ge n-c\), then P contains a standard example \(S_d\) with \(d\ge n-f(c)\). From below, we show that \(f(c)={\varOmega }(c^{4/3})\). On the other hand, we also prove an analogous result for fractional dimension, and in this setting f(c) is linear in c. Here the result is best possible up to the value of the multiplicative constant.     

Capacity inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow \(x^0\), the inverse minimum cost flow problem is to modify the capacity vector or the cost vector as little as possible to make \(x^0\) form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the capacity inverse minimum cost flow problems under the weighted Hamming distance, where we use the weighted Hamming distance to measure the modification of the arc capacities. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in \(O(n\cdot m^2)\) time.     

A group of continuous self-maps on a topological groupoid

The group of bisections of groupoids plays an important role in the study of Lie groupoids. In this paper another construction is introduced. Indeed, for a topological groupoid G, the set of all continuous self-maps f on G such that (x, f(x)) is a composable pair for every \(x\in G\), is denoted by \(S_G\). We show that \(S_G\) by a natural binary operation is a monoid. \(S_G(\alpha )\), the group of units in \(S_G\) precisely consists of those \(f\in S_G\) such that the map \(x\mapsto xf(x)\) is a bijection on G. Similar to the group of bisections, \(S_G(\alpha )\) acts on G from the right and on the space of continuous self-maps on G from the left. It is proved that \(S_G(\alpha )\) with the compact- open topology inherited from C(G, G) is a left topological group. For a compact Hausdorff groupoid G it is proved that the group of bisections of \(G^2\) is isomorphic to the group \(S_G(\alpha )\) and the group of transitive bisections of G, \(Bis_T(G)\), is embedded in \(S_G(\alpha )\), where \(G^2\) is the groupoid of all composable pairs.     

2-Arc-transitive cyclic covers of $$K_{n,n}$$

In this paper, a complete classification is achieved of all the regular covers of the complete bipartite graphs \(K_{n,n}\) with cyclic covering transformation group, whose fibre-preserving automorphism group acts 2-arc-transitively. All these covers consist of one threefold covers of \(K_{6,6}\), one twofold cover of \(K_{12, 12}\) and one infinite family X(r, p) of p-fold covers of \(K_{p^r,p^r}\) with p a prime and r an integer such that \(p^r\ge 3\). This infinite family X(r, p) can be derived by a very simple and nice voltage assignment f as follows: \(X(r, p)=K_{p^r, p^r}\times _f \mathbb {Z}_p\), where \(K_{p^r, p^r}\) is a complete bipartite graph with the bipartition \(V=\{ \alpha \bigm |\alpha \in V(r,p)\}\cup \{ \alpha '\bigm |\alpha \in V(r,p)\}\) for the r-dimensional vector space V(r, p) over the field of order p and \(f_{\alpha ,\beta '}=\sum _{i=1}^ra_ib_i,\,\, \mathrm{for\,\,all}\,\,\alpha =(a_i)_r, \beta =(b_i)_r\in V(r,p)\).     

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.     

Skew <Emphasis Type="Italic">n</Emphasis>-derivation on prime and semi prime rings

Let \(n \ge 2\) be a fixed integer, R be a noncommutative n!-torsion free ring and I be any non zero ideal of R. In this paper we have proved the following results; (i) If R is a prime ring and there exists a symmetric skew n-derivation \(D: R^n \rightarrow R\) associated with the automorphism \(\sigma \) on R,  such that the trace function \(\delta : R \rightarrow R \) of D satisfies \([\delta (x), \sigma (x)] =0\), for all \(x\in I,\) then \(D=0;\,\)(ii) If R is a semi prime ring and the trace function \(\delta ,\) commuting on I,  satisfies \([\delta (x), \sigma (x)]\in Z\), for all \(x \in I,\) then \([\delta (x), \sigma (x)] = 0 \), for all \(x \in I.\) Moreover, we have proved some annihilating conditions for algebraic identity involving multiplicative(generalized) derivation.     

Generalized Bernstein Operators on the Classical Polynomial Spaces

We study generalizations of the classical Bernstein operators on the polynomial spaces \(\mathbb {P}_{n}[a,b]\), where instead of fixing \(\mathbf {1}\) and x, we reproduce exactly \(\mathbf {1}\) and a polynomial \(f_1\), strictly increasing on [a, b]. We prove that for sufficiently large n, there always exist generalized Bernstein operators fixing \(\mathbf {1}\) and \(f_1\). These operators are defined by non-decreasing sequences of nodes precisely when \(f_1^\prime > 0\) on (a, b), but even if \(f_1^\prime \) vanishes somewhere inside (a, b), they converge to the identity.     

A unifying approach to the Margolis–Meakin and Birget–Rhodes group expansion

Let G be a group. We show that the Birget–Rhodes prefix expansion \(G^{Pr}\) and the Margolis–Meakin expansion M(X; f) of G with respect to \(f:X\rightarrow G\) can be regarded as inverse subsemigroups of a common E-unitary inverse semigroup P. We construct P as an inverse subsemigroup of an E-unitary inverse monoid \(U/\zeta \) which is a homomorphic image of the free product U of the free semigroup \(X^+\) on X and G. The semigroup P satisfies a universal property with respect to homomorphisms into the permissible hull C(S) of a suitable E-unitary inverse semigroup S, with \(S/\sigma _S=G\), from which the characterizing universal properties of \(G^{Pr}\) and M(X; f) can be recaptured easily.     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

O n ( m n,n, m n,m) relative differe nce sets with $$\text {gcd}( m,n)=1$$gcd( m,n)=1

There has been much research on \((p^{a},p^{b},p^{a},p^{a-b})\) relative difference sets with p a prime, while there are only a few results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\). The non-existence results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\) have only been obtained for the following five cases: (1) \(m=p,\ n=q,\ p>q\); (2) \(m=pq,\ n=3,\ p,q>3\); (3) \(m=4,\ n=p\); (4) \(m=2\) and (5) \(n=p\), where p, q are distinct odd primes. For the existence results, there are only four constructions of semi-regular relative difference sets in groups of size not a prime power with the forbidden subgroup having size larger than 2. In this paper, we present some more non-existence results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\). In particular, our result is a generalization of the main result of Hiramine’s work (J Comb Theory Ser A 117(7):996–1003, 2010). Meanwhile, we give a construction of non-abelian (16q, q, 16q, 16) relative difference sets, where q is a prime power with \(q\equiv 1\pmod {4}\) and \(q>4.2\times 10^{8}\). This is the third known infinite classes of non-abelian semi-regular relative difference sets.