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.     

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

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.     

On a conjecture of Stein

Stein (Pac J Math 59:567–575, 1975) proposed the following conjecture: if the edge set of \(K_{n,n}\) is partitioned into n sets, each of size n, then there is a partial rainbow matching of size \(n-1\). He proved that there is a partial rainbow matching of size \(n(1-\frac{D_n}{n!})\), where \(D_n\) is the number of derangements of [n]. This means that there is a partial rainbow matching of size about \((1- \frac{1}{e})n\). Using a topological version of Hall’s theorem we improve this bound to \(\frac{2}{3}n\).     

On the estimates of the upper and lower bounds of Ramanujan primes

For \(n\ge 1\), the nth Ramanujan prime is defined as the least positive integer \(R_{n}\) such that for all \(x\ge R_{n}\), the interval \((\frac{x}{2}, x]\) has at least n primes. Let \(p_{i}\) be the ith prime and \(R_{n}=p_{s}\). Sondow, Laishram, and other scholars gave a series of upper bounds of s. In this paper we establish several results giving estimates of upper and lower bounds of Ramanujan primes. Using these estimates, we discuss a conjecture on Ramanujan primes of Sondow–Nicholson–Noe and prove that if \(n>10^{300}\), then \(\pi (R_{mn})\le m\pi (R_{n})\) for \(m\ge 1\).     

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

On Star–Wheel Ramsey Numbers

For two given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the least integer r such that for every graph G on r vertices, either G contains a \(G_1\) or \(\overline{G}\) contains a \(G_2\). In this note, we determined the Ramsey number \(R(K_{1,n},W_m)\) for even m with \(n+2\le m\le 2n-2\), where \(W_m\) is the wheel on \(m+1\) vertices, i.e., the graph obtained from a cycle \(C_m\) by adding a vertex v adjacent to all vertices of the \(C_m\).     

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.     

Hyperinvariant Subspace Problem for Some Classes of Operators

An n-normal operator may be defined as an \(n \times n\) operator matrix with entries that are mutually commuting normal operators and an operator \(T \in \mathcal {B(H)}\) is quasi-nM-hyponormal (for \(n \in \mathbb {N}\)) if it is unitarily equivalent to an \(n \times n\) upper triangular operator matrix \((T_{ij})\) acting on \(\mathcal {K}^{(n)}\), where \(\mathcal {K}\) is a separable complex Hilbert space and the diagonal entries \(T_{jj}\) \((j = 1,2,\ldots , n)\) are M-hyponormal operators in \(\mathcal {B(K)}\). This is an extended notion of n-normal operators. We prove a necessary and sufficient condition for an \(n \times n\) triangular operator matrix to have Bishop’s property \((\beta )\). This leads us to study the hyperinvariant subspace problem for an \(n \times n\) triangular operator matrix.     

On a Generalization for Tribonacci Quaternions

Let \(V_{n}\) denote the third order linear recursive sequence defined by the initial values \(V_{0}\), \(V_{1}\) and \(V_{2}\) and the recursion \(V_{n}=rV_{n-1}+sV_{n-2}+tV_{n-3}\) if \(n\ge 3\), where r, s, and t are real constants. The \(\{V_{n}\}_{n\ge 0}\) are generalized Tribonacci numbers and reduce to the usual Tribonacci numbers when \(r=s=t=1\) and to the 3-bonacci numbers when \(r=s=1\) and \(t=0\). In this study, we introduced a quaternion sequence which has not been introduced before. We show that the new quaternion sequence that we introduced includes the previously introduced Tribonacci, Padovan, Narayana and third order Jacobsthal quaternion sequences. We obtained the Binet formula, summation formula and the norm value for this new quaternion sequence.     

Random Walks in the Hyperbolic Plane and the Minkowski Question Mark Function

Consider \(G=SL_2(\mathbb {Z})/\{\pm I\}\) acting on the complex upper half plane H by \(h_M(z)=\frac{az\,+\,b}{cz\,+\,d}\) for \(M \in G\). Let \(D=\{z \in H: |z|\ge 1, |\mathfrak {R}(z)|\le 1/2\}\). We consider the set \({\mathcal {E}} \subset G\) with the nine elements M, different from the identity, such that \(\mathrm{tr\,}(MM^T)\le 3\). We equip the tiling of H defined by \(\mathbb {D}=\{h_M(D){:}\, M \in G\}\) with a graph structure where the neighbours are defined by \(h_M(D) \cap h_{M'}(D) \ne \emptyset \), equivalently \(M^{-1}M' \in {\mathcal {E}}\). The present paper studies several Markov chains related to the above structure. We show that the simple random walk on the above graph converges a.s. to a point X of the real line with the same distribution of \(S_2 W^{S_1}\), where \(S_1,S_2,W\) are independent with \(\Pr (S_i=\pm 1)=1/2\) and where W is valued in (0, 1) with distribution \(\Pr (W<w)=\mathbf ? (w)\). Here \(\mathbf ? \) is the Minkowski function. If \(K_1, K_2, \ldots \) are i.i.d with distribution \(\Pr (K_i=n)= 1/2^n\) for \(n=1,2,\ldots \), then \(W= \frac{1}{K_1+\frac{1}{K_2+\ldots }}\): this known result (Isola in Appl Math 5:1067–1090, 2014) is derived again here.     

Fractional Differentiability for Solutions of Nonlinear Elliptic Equations

We study nonlinear elliptic equations in divergence form

$$\text {div }{\mathcal A}(x,Du)=\text {div } G.$$

When \({\mathcal A}\) has linear growth in D u, and assuming that \(x\mapsto {\mathcal A}(x,\xi )\) enjoys \(B^{\alpha }_{\frac {n}\alpha , q}\) smoothness, local well-posedness is found in \(B^{\alpha }_{p,q}\) for certain values of \(p\in [2,\frac {n}{\alpha })\) and \(q\in [1,\infty ]\). In the particular case \({\mathcal A}(x,\xi )=A(x)\xi \), G = 0 and \(A\in B^{\alpha }_{\frac {n}\alpha ,q}\), \(1\leq q\leq \infty \), we obtain \(Du\in B^{\alpha }_{p,q}\) for each \(p<\frac {n}\alpha \). Our main tool in the proof is a more general result, that holds also if \({\mathcal A}\) has growth s?1 in D u, 2 ≤ s ≤ n, and asserts local well-posedness in L ^q for each q > s, provided that \(x\mapsto {\mathcal A}(x,\xi )\) satisfies a locally uniform VMO condition.

     

Hadamard full propelinear codes of type Q; rank and kernel

Hadamard full propelinear codes (\(\mathrm{HFP}\)-codes) are introduced and their equivalence with Hadamard groups is proven; on the other hand, the equivalence of Hadamard groups, relative (4n, 2, 4n, 2n)-difference sets in a group, and cocyclic Hadamard matrices, is already known. We compute the available values for the rank and dimension of the kernel of \(\mathrm{HFP}\)-codes of type Q and we show that the dimension of the kernel is always 1 or 2. We also show that when the dimension of the kernel is 2 then the dimension of the kernel of the transposed code is 1 (so, both codes are not equivalent). Finally, we give a construction method such that from an \(\mathrm{HFP}\)-code of length 4n, dimension of the kernel \(k=2\), and maximum rank \(r=2n\), we obtain an \(\mathrm{HFP}\)-code of double length 8n, dimension of the kernel \(k=2\), and maximum rank \(r=4n\).     

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.     

On the gaps between non-zero Fourier coefficients of cusp forms of higher weight

We show that if a modular cuspidal eigenform f of weight 2k is 2-adically close to an elliptic curve \(E/\mathbb {Q}\), which has a cyclic rational 4-isogeny, then n-th Fourier coefficient of f is non-zero in the short interval \((X, X + cX^{\frac{1}{4}})\) for all \(X \gg 0\) and for some \(c > 0\). We use this fact to produce non-CM cuspidal eigenforms f of level \(N>1\) and weight \(k > 2\) such that \(i_f(n) \ll n^{\frac{1}{4}}\) for all \(n \gg 0\).     

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

Partial permutation decoding for binary linear and $$Z_4$$-linear Hadamard codes

In this paper, s-\({\text {PD}}\)-sets of minimum size \(s+1\) for partial permutation decoding for the binary linear Hadamard code \(H_m\) of length \(2^m\), for all \(m\ge 4\) and \(2 \le s \le \lfloor {\frac{2^m}{1+m}}\rfloor -1\), are constructed. Moreover, recursive constructions to obtain s-\({\text {PD}}\)-sets of size \(l\ge s+1\) for \(H_{m+1}\) of length \(2^{m+1}\), from an s-\({\text {PD}}\)-set of the same size for \(H_m\), are also described. These results are generalized to find s-\({\text {PD}}\)-sets for the \({\mathbb {Z}}_4\)-linear Hadamard codes \(H_{\gamma , \delta }\) of length \(2^m\), \(m=\gamma +2\delta -1\), which are binary Hadamard codes (not necessarily linear) obtained as the Gray map image of quaternary linear codes of type \(2^\gamma 4^\delta \). Specifically, s-PD-sets of minimum size \(s+1\) for \(H_{\gamma , \delta }\), for all \(\delta \ge 3\) and \(2\le s \le \lfloor {\frac{2^{2\delta -2}}{\delta }}\rfloor -1\), are constructed and recursive constructions are described.     

Matrix Gegenbauer Polynomials: The $$2\times 2$$ Fundamental Cases

In this paper, we exhibit explicitly a sequence of \(2 \times 2\) matrix valued orthogonal polynomials with respect to a weight \(W_{p,n}\), for any pair of real numbers p and n such that \(0<p<n\). The entries of these polynomiales are expressed in terms of the Gegenbauer polynomials \(C_k^\lambda \). The corresponding three-term recursion relations are also given, and we make some studies of the algebra of differential operators associated with the weight \(W_{p,n}\).     

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.     

Triviality of Iwasawa module associated to some abelian fields of prime conductors

Let p be an odd prime number and \(\ell \) an odd prime number dividing \(p-1\). We denote by \(F=F_{p,\ell }\) the real abelian field of conductor p and degree \(\ell \), and by \(h_F\) the class number of F. For a prime number \(r \ne p,\,\ell \), let \(F_{\infty }\) be the cyclotomic \(\mathbb {Z}_r\)-extension over F, and \(M_{\infty }/F_{\infty }\) the maximal pro-r abelian extension unramified outside r. We prove that \(M_{\infty }\) coincides with \(F_{\infty }\) and consequently \(h_F\) is not divisible by r when r is a primitive root modulo \(\ell \) and r is smaller than an explicit constant depending on p.