Rainbow Spanning Subgraphs of Small Diameter in Edge-Colored Complete Graphs

Let s(n, t) be the maximum number of colors in an edge-coloring of the complete graph \(K_n\) that has no rainbow spanning subgraph with diameter at most t. We prove \(s(n,t)={\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) }+1\) for \(n,t\ge 3\), while \(s(n,2)={\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) }+\left\lfloor {\frac{n-1}{2}}\right\rfloor \) for \(n\ne 4\) (and \(s(4,2)=2\)).     

Rainbow matchings in bipartite multigraphs

Suppose that k is a non-negative integer and a bipartite multigraph G is the union of

$$\begin{aligned} N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1) \end{aligned}$$

matchings \(M_1,\dots ,M_N\), each of size n. We show that G has a rainbow matching of size \(n-k\), i.e. a matching of size \(n-k\) with all edges coming from different \(M_i\)’s. Several choices of the parameter k relate to known results and conjectures.

     

Map determined by rank-$$\varvec{}$$ matrice for relatively mall $$\varvec{}$$

Let n and s be integers such that \(1\le s<\frac{n}{2}\), and let \(M_n(\mathbb {K})\) be the ring of all \(n\times n\) matrices over a field \(\mathbb {K}\). Denote by \([\frac{n}{s}]\) the least integer m with \(m\ge \frac{n}{s}\). In this short note, it is proved that if \(g:M_n(\mathbb {K})\rightarrow M_n(\mathbb {K})\) is a map such that \(g\left( \sum _{i=1}^{[\frac{n}{s}]}A_i\right) =\sum _{i=1}^{[\frac{n}{s}]}g(A_i)\) holds for any \([\frac{n}{s}]\) rank-s matrices \(A_1,\ldots ,A_{[\frac{n}{s}]}\in M_n(\mathbb {K})\), then \(g(x)=f(x)+g(0)\), \(x\in M_n(\mathbb {K})\), for some additive map \(f:M_n(\mathbb {K})\rightarrow M_n(\mathbb {K})\). Particularly, g is additive if \(char\mathbb {K}\not \mid \left( [\frac{n}{s}]-1\right) \).     

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

Some Estimates of Higher Order Riesz Transform Related to Schrödinger Type Operators

In this paper we consider the Schrödinger type operators \(H_2=(-\Delta)^2 +V^2\), where the nonnegative potential V belongs to the reverse Hölder class \(B_{q_{_1}}\) for \(q_{_1}\geq \frac{n}{2}, n\geq 5\). The L ^p and weak type (1, 1) estimates of higher order Riesz transform \(\nabla^2H^{-\frac{1}{2}}_2 \) related to Schrödinger type operators H ₂ are obtained. In particular, \(\nabla^2H^{-\frac{1}{2}}_2 \) is a Calderón-Zygmund operator if V?∈?B _2n or \(V\in B_\frac{n}{2}\) and there exists a constant C such that V(x)?≤?Cm(x,V)².     

On sums of binomial coefficients involving Catalan and Delannoy numbers modulo $$p^2$$

In this paper, we prove some congruences conjectured by Z.-W. Sun: For any prime \(p>3\), we determine

$$\begin{aligned} \sum \limits _{k = 0}^{p - 1} {\frac{{{C_k}C_k^{(2)}}}{{{{27}^k}}}} \quad {\text { and }}\quad \sum \limits _{k = 1}^{p - 1} {\frac{{\left( {\begin{array}{l} {2k} \\ {k - 1} \\ \end{array}} \right) \left( { \begin{array}{l} {3k} \\ {k - 1} \\ \end{array} } \right) }}{{{{27}^k}}}} \end{aligned}$$

modulo \(p^2\), where \(C_k=\frac{1}{k+1}\left( {\begin{array}{c}2k\\ k\end{array}}\right) \) is the k-th Catalan number and \(C_k^{(2)}=\frac{1}{2k+1}\left( {\begin{array}{c}3k\\ k\end{array}}\right) \) is the second-order Catalan numbers of the first kind. And we prove that

$$\begin{aligned} \sum _{k=1}^{p-1}\frac{D_k}{k}\equiv -q_p(2)+pq_p(2)^2\pmod {p^2}, \end{aligned}$$

where \(D_n=\sum _{k=0}^{n}\left( {\begin{array}{c}n\\ k\end{array}}\right) \left( {\begin{array}{c}n+k\\ k\end{array}}\right) \) is the n-th Delannoy number and \(q_p(2)=(2^{{p-1}}-1)/p\) is the Fermat quotient.

     

Counting polynomial subset sums

Let D be a subset of a finite commutative ring R with identity. Let \(f(x)\in R[x]\) be a polynomial of degree d. For a nonnegative integer k, we study the number \(N_f(D,k,b)\) of k-subsets S in D such that

$$\begin{aligned} \sum _{x\in S} f(x)=b. \end{aligned}$$

In this paper, we establish several bounds for the difference between \(N_f(D,k, b)\) and the expected main term \(\frac{1}{|R|}{|D|\atopwithdelims ()k}\), depending on the nature of the finite ring R and f. For \(R=\mathbb {Z}_n\), let \(p=p(n)\) be the smallest prime divisor of n, \(|D|=n-c \ge C_dn p^{-\frac{1}{d}}\,+\,c\) and \(f(x)=a_dx^d +\cdots +a_0\in \mathbb {Z}[x]\) with \((a_d, \ldots , a_1, n)=1\). Then

$$\begin{aligned} \left| N_f(D, k, b)-\frac{1}{n}{n-c \atopwithdelims ()k}\right| \le {\delta (n)(n-c)+(1-\delta (n))\left( C_dnp^{-\frac{1}{d}}+c\right) +k-1\atopwithdelims ()k}, \end{aligned}$$

answering an open question raised by Stanley (Enumerative combinatorics, 1997) in a general setting, where \(\delta (n)=\sum _{i\mid n, \mu (i)=-1}\frac{1}{i}\) and \(C_d=e^{1.85d}\). Furthermore, if n is a prime power, then \(\delta (n) =1/p\) and one can take \(C_d=4.41\). Similar and stronger bounds are given for two more cases. The first one is when \(R=\mathbb {F}_q\), a q-element finite field of characteristic p and f(x) is general. The second one is essentially the well-known subset sum problem over an arbitrary finite abelian group. These bounds extend several previous results.

     

Construction of sign-changing solutions for a harmonic equation with subcritical exponent

In this paper, we study the harmonic equation involving subcritical exponent \((P_{\varepsilon })\): \( \Delta u = 0 \), in \(\mathbb {B}^n\) and \(\displaystyle \frac{\partial u}{\partial \nu } + \displaystyle \frac{n-2}{2}u = \displaystyle \frac{n-2}{2} K u^{\frac{n}{n-2}-\varepsilon }\) on \( \mathbb {S}^{n-1}\) where \(\mathbb {B}^n \) is the unit ball in \(\mathbb {R}^n\), \(n\ge 5\) with Euclidean metric \(g_0\), \(\partial \mathbb {B}^n = \mathbb {S}^{n-1}\) is its boundary, K is a function on \(\mathbb {S}^{n-1}\) and \(\varepsilon \) is a small positive parameter. We construct solutions of the subcritical equation \((P_{\varepsilon })\) which blow up at two different critical points of K. Furthermore, we construct solutions of \((P_{\varepsilon })\) which have two bubbles and blow up at the same critical point of K.     

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

Edge Roman Domination on Graphs

An edge Roman dominating function of a graph G is a function \(f:E(G) \rightarrow \{0,1,2\}\) satisfying the condition that every edge e with \(f(e)=0\) is adjacent to some edge \(e'\) with \(f(e')=2\). The edge Roman domination number of G, denoted by \(\gamma '_R(G)\), is the minimum weight \(w(f) = \sum _{e\in E(G)} f(e)\) of an edge Roman dominating function f of G. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if G is a graph of maximum degree \(\Delta \) on n vertices, then \(\gamma _R'(G) \le \lceil \frac{\Delta }{\Delta +1} n \rceil \). While the counterexamples having the edge Roman domination numbers \(\frac{2\Delta -2}{2\Delta -1} n\), we prove that \(\frac{2\Delta -2}{2\Delta -1} n + \frac{2}{2\Delta -1}\) is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of k-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on n vertices is at most \(\frac{6}{7}n\), which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain \(K_{2,3}\) as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.     

Rigidity theorem for integral pinched shrinking Ricci solitons

We prove that an n-dimensional, \(n\ge 4\), compact gradient shrinking Ricci soliton satisfying a \(L^{\frac{n}{2}}\)-pinching condition is isometric to a quotient of the round \(\mathbb {S}^n\), which improves the rigidity theorem given by Catino (Integral pinched shrinking Ricci solitons, 2016), in dimension \(4\le n\le 6\).     

Induced Cycles in Graphs

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by \(c_\mathrm{ind}(G)\). We prove that if G is an r-regular graph of order n, then \(c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}\) and we prove that if G is a cubic, claw-free graph on order n, then \(c_\mathrm{ind}(G) > \frac{13}{20}n\) and this bound is asymptotically best possible.     

New lower bounds for the Shannon capacity of odd cycles

The Shannon capacity of a graph G is defined as \(c(G)=\sup _{d\ge 1}(\alpha (G^d))^{\frac{1}{d}},\) where \(\alpha (G)\) is the independence number of G. The Shannon capacity of the cycle \(C_5\) on 5 vertices was determined by Lovász in 1979, but the Shannon capacity of a cycle \(C_p\) for general odd p remains one of the most notorious open problems in information theory. By prescribing stabilizers for the independent sets in \(C_p^d\) and using stochastic search methods, we show that \(\alpha (C_7^5)\ge 350\), \(\alpha (C_{11}^4)\ge 748\), \(\alpha (C_{13}^4)\ge 1534\), and \(\alpha (C_{15}^3)\ge 381\). This leads to improved lower bounds on the Shannon capacity of \(C_7\) and \(C_{15}\): \(c(C_7)\ge 350^{\frac{1}{5}}> 3.2271\) and \(c(C_{15})\ge 381^{\frac{1}{3}}> 7.2495\).     

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.     

Parity check matrices and product representations of squares

Let \(N_{\mathbb{F}} \)(n,k,r) denote the maximum number of columns in an n-row matrix with entries in a finite field \(\mathbb{F}\) in which each column has at most r nonzero entries and every k columns are linearly independent over \(\mathbb{F}\). We obtain near-optimal upper bounds for \(N_{\mathbb{F}} \)(n,k,r) in the case k > r. Namely, we show that \(N_\mathbb{F} (n,k,r) \ll n^{\frac{r}{2} + \frac{{cr}}{k}} \) where \(c \approx \frac{4}{3}\) for large k. Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependencies. We present additional applications of this method to a problem on hypergraphs and a problem in combinatorial number theory.     

A Munn type representation of abundant semigroups with a multiplicative ample transversal

In this note, we consider the Erd?s–Straus Diophantine equation

$$\begin{aligned} \frac{c}{n}=\frac{1}{x} + \frac{1}{y} + \frac{1}{z}, \end{aligned}$$

where n and c are positive integers with \(\gcd (n, c) = 1\). We provide a formula for the number f(n, c) of all positive integral solutions (x, y, z) of the equation. In 1948, Erd?s and Straus conjectured that \(f(n,4) \ge 1,\) for all integers \(n \ge 2\). Here, we solve the conjecture for a special case of n.

     

On the densities of rational multiples

For two subsets of natural numbers \( A,B \subset \mathbb{N} \), define the set of rational numbers \( \mathcal{M}\left( {A,B} \right) \) with the elements represented by m/n, where m and n are coprime, m is divisible by some a ∈ A, and n is divisible by some b ∈ B. Let I be some interval of positive real numbers and \( \mathcal{F}_x^I \) denote the set of rational numbers m/n ∈ I such that m and n are coprime and n ? x. The analogue to the Erdös–Davenport theorem about multiples is proved: under some constraints on I, the limits \( {{{\sum {\left\{ {\frac{1}{{mn}}:\frac{m}{n} \in \mathcal{F}_x^I \cap \mathcal{M}\left( {A,B} \right)} \right\}} }} \left/ {{\sum {\left\{ {\frac{1}{{mn}}:\frac{m}{n} \in \mathcal{F}_x^I} \right\}} }} \right.} \) exist for all subsets \( A,B \subset \mathbb{N} \) as x → ∞.     

Répartitio n simulta née de S( n) et $$ S( n+1)$$ S( n+1) da ns les progressio ns arithmétiques

If \(q\ge 2\) is an integer, we denote by \(S_q(n)\) the sum of the digits in base q of the positive integer n and by \(v_q(n)\) its q-adic valuation. The goal of this work is to study exponential sums of the form \(\displaystyle \sum \nolimits _{n\le x}\exp \big (2i\pi \big (\frac{l}{m} S_q(n)+\frac{k}{m'}S_q(n+1)+\theta n\big )\big )\) in order to prove some statistical properties of integers n for which \(S_q(n)\) and \(S_q(n+1)\) belong to given arithmetic progressions. This extends the results obtained by Gelfond in 1968 and those obtained by Mauduit–Sárközy in 1996.     

Euclidean Distance Between Haar Orthogonal and Gaussian Matrices

In this work, we study a version of the general question of how well a Haar-distributed orthogonal matrix can be approximated by a random Gaussian matrix. Here, we consider a Gaussian random matrix \(Y_n\) of order n and apply to it the Gram–Schmidt orthonormalization procedure by columns to obtain a Haar-distributed orthogonal matrix \(U_n\). If \(F_i^m\) denotes the vector formed by the first m-coordinates of the ith row of \(Y_n-\sqrt{n}U_n\) and \(\alpha \,=\,\frac{m}{n}\), our main result shows that the Euclidean norm of \(F_i^m\) converges exponentially fast to \(\sqrt{ \big (2-\frac{4}{3} \frac{(1-(1 -\alpha )^{3/2})}{\alpha }\big )m}\), up to negligible terms. To show the extent of this result, we use it to study the convergence of the supremum norm \(\epsilon _n(m)\,=\,\sup _{1\le i \le n, 1\le j \le m} |y_{i,j}- \sqrt{n}u_{i,j}|\) and we find a coupling that improves by a factor \(\sqrt{2}\) the recently proved best known upper bound on \(\epsilon _n(m)\). Our main result also has applications in Quantum Information Theory.     

Eichler’s commutation relation and some other invariant subspaces of Hecke operators

Let k be an odd positive integer, L a lattice on a regular positive definite k-dimensional quadratic space over \(\mathbb {Q}\), \(N_L\) the level of L, and \(\mathscr {M}(L)\)  be the linear space of \(\theta \)-series attached to the distinct classes in the genus of L. We prove that, for an odd prime \(p|N_L\), if \(L_p=L_{p,1}\,\bot \, L_{p,2}\), where \(L_{p,1}\) is unimodular, \(L_{p,2}\) is (p)-modular, and \(\mathbb {Q}_pL_{p,2}\) is anisotropic, then \(\mathscr {M}(L;p):=\) \(\mathscr {M}(L)\) \(+T_{p^2}.\) \(\mathscr {M}(L)\)  is stable under the Hecke operator \(T_{p^2}\). If \(L_2\) is isometric to \(\left( \begin{array}{ll}0&{}\frac{1}{2}\\ \frac{1}{2}&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle \varepsilon \rangle \) or \(\left( \begin{array}{ll}0&{}\frac{1}{2}\\ \frac{1}{2}&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle 2\varepsilon \rangle \) or \(\left( \begin{array}{ll}0&{}1\\ 1&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle \varepsilon \rangle \) with \(\varepsilon \in \mathbb {Z}_2^{\times }\) and \(\kappa :=\frac{k-1}{2}\), then \(\mathscr {M}(L;2):=T_{2^2}.\mathscr {M}(L)+T_{2^2}^2.\,\mathscr {M}(L)\) is stable under the Hecke operator \(T_{2^2}\). Furthermore, we determine some invariant subspaces of the cusp forms for the Hecke operators.