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

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.     

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

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

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

Line complexity asymptotics of polynomial cellular automata

Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence \(a_T(k)\), which counts, for each k, the number of coefficient strings of length k that occur in the automaton. We begin with the modulo 2 case. For a polynomial \(T(x)=c_0+c_1x+\dots +c_nx^n\) with \(c_0,c_n\ne ~0\), we construct odd and even parts of the polynomial from the strings \(0c_1c_3c_5\cdots c_{1+2\lfloor (n-1)/2\rfloor }\) and \(c_0c_2c_4\cdots c_{2\lfloor n/2\rfloor }\), respectively. We prove that \(a_T(k)\) satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we consider an abstract generating function \(\phi (z)=\sum _{k=1}^\infty \alpha (k)z^k\) which satisfies a functional equation relating \(\phi (z)\) and \(\phi (z^p)\). We show that there is a continuous, piecewise quadratic function f on [1 / p, 1] for which \(\lim _{k\rightarrow \infty }(\alpha (k)/k^2-~f(p^{-\langle \log _p k\rangle })) = 0\) (here \(\langle y\rangle =y-\lfloor y\rfloor \)). We use this result to show that for certain positive integer sequences \(s_k(x)\rightarrow \infty \) with a parameter \(x\in [1/p,1]\), the ratio \(\alpha (s_k(x))/s_k(x)^2\) tends to f(x), and that the limit superior and inferior of \(\alpha (k)/k^2\) are given by the extremal values of f.     

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.     

Beatty sequences and prime numbers with restrictions on strongly <Emphasis Type="Italic">q</Emphasis>-additive functions

We estimate exponential sums over a non-homogenous Beatty sequence with restriction on strongly q-additive functions. We then apply our result in a few special cases to obtain an asymptotic formula for the number of primes \(p=\lfloor \alpha n +\beta \rfloor \) and \(f(p)\equiv a (\mathrm{mod\,}b)\), with \(n\ge N \), where \(\alpha \), \(\beta \) are real numbers and f is a strongly q-additive function (for example, the sum of digits function in base q is a strongly q-additive function). We also prove that for any fixed integer \(k\ge 3 \), all sufficiently large \(N\equiv k (\mathrm{mod\,}2) \) could be represented as a sum of k prime numbers from a Beatty sequence with restriction on strongly q-additive functions.     

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

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

Newforms with rational coefficients

We consider the set of classical newforms with rational coefficients and no complex multiplication. We study the distribution of quadratic twist-classes of these forms with respect to weight k and minimal level N. We conjecture that for each weight \(k \ge 6\), there are only finitely many classes. In large weights, we make this conjecture effective: in weights \(18 \le k \le 24\), all classes have \(N \le 30\); in weights \(26 \le k \le 50\), all classes have \(N \in \{2,6\}\); and in weights \(k \ge 52\), there are no classes at all. We study some of the newforms appearing on our conjecturally complete list in more detail, especially in the cases \(N=2\), 3, 4, 6, and 8, where formulas can be kept nearly as simple as those for the classical case \(N=1\).     

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

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.

     

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.

     

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

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.     

Monochromatic Solutions for Multi-Term Unknowns

Given integers \(k\ge 2\), \(n \ge 2\), \(m \ge 2\) and \( a_1,a_2,\ldots ,a_m \in {\mathbb {Z}}{\backslash }{\{0\}}\), and let \(f(z)= \sum _{j=0}^{n}c_jz^j\) be a polynomial of integer coefficients with \(c_n>0\) and \((\sum _{i=1}^ma_i)|f(z)\) for some integer z. For a k-coloring of \([N]=\{1,2,\ldots ,N\}\), we say that there is a monochromatic solution of the equation \(a_1x_1+a_2x_2+\cdots +a_mx_m=f(z)\) if there exist pairwise distinct \(x_1,x_2,\ldots ,x_m\in [N]\) all of the same color such that the equation holds for some \(z\in \mathbb {Z}\). Problems of this type are often referred to as Ramsey-type problems. In this paper, it is shown that if \(a_i>0\) for \(1\le i\le m\), then there exists an integer \(N_0=N(k,m,n)\) such that for \(N\ge N_0\), each k-coloring of [N] contains a monochromatic solution \(x_1,x_2,\ldots ,x_m\) of the equation \(a_1x_1+a_2x_2+ \cdots +a_mx_m= f(z)\). Moreover, if n is odd and there are \(a_i\) and \(a_j\) such that \(a_ia_j<0\) for some \(1 \le i\ne j\le m\), then the assertion holds similarly.     

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 a (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-visual cryptography scheme

In this paper we give an explicit construction of basis matrices for a (k, n)-visual cryptography scheme \((k,n){\hbox {-}}\mathrm{VCS}\) for integers k and n with \(2\le k \le n\). In balanced VCS every set of participants with equal cardinality has same relative contrast. The VCS constructed in this paper is a balanced \((k,n){\hbox {-}}\mathrm{VCS}\) for general k. Also we obtain a formula for pixel expansion and relative contrast. We also prove that our construction gives optimal contrast and minimum pixel expansion when \(k=n\) and \(n-1\).