The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

Permutations with small maximal k-consecutive sums

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i?{\sum }_{j=0}^{k?1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $\mathsf{msum}(n,k)?min\left\{max\{s_i:i=1,\dots ,n\}?\frac{k(n+1)}{2}:\pi \in S_n\right\},$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathsf{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathsf{msum}(n,3)$, $\mathsf{msum}(n,4)$ and $\mathsf{msum}(n,6)$ for any $n$.     

A combinatorial proof of a formula for the Lucas-Narayana polynomials

In 2020, Bennett, Carrillo, Machacek and Sagan gave a polynomial generalization of the Narayana numbers and conjectured that these polynomials have positive integer coefficients for $1\le k\le n$ and for $n\ge 1$. In 2020, Sagan and Tirrell used a powerful algebraic method to prove this conjecture (in fact, they extend and prove the conjecture for more than just the type A case). In this paper we give a combinatorial proof of a formula satisfied by the Lucas-Narayana polynomials described by Bennett et al. This gives a combinatorial proof that these polynomials have positive integer coefficients. A corollary of our main result establishes a parallel theorem for the FiboNarayana numbers $N_{n,k,F}$, providing a combinatorial proof of the conjecture that these are positive integers for $n\ge 1$.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Separable discrete functions: Recognition and sufficient conditions

A discrete function of $n$ variables is a mapping $g:X_1\times \dots \times X_n\to A$, where $X_1,\dots ,X_n$, and $A$ are arbitrary finite sets. Function $g$ is called separable if there exist $n$ functions $g_i:X_i\to A$ for $i=1,\dots ,n$, such that for every input $x_1,\dots ,x_n$ the function $g(x_1,\dots ,x_n)$ takes one of the values $g_1\left(x_1\right),\dots ,g_n\left(x_n\right)$. Given a discrete function $g$, it is an interesting problem to ask whether $g$ is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of $n$ variables is known only for $n=2$. In this paper we will show that a slightly more general recognition problem, when $g$ is not fully but only partially defined, is NP-complete for $n\ge 3$. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for $n\ge 4$.The general recognition problem contains the above mentioned special case for $n=2$. This case is well-studied in the context of game theory, where (separable) discrete functions of $n$ variables are referred to as (assignable) $n$-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of $n$ variables for any $n$, thus generalizing the above result known for $n=2$. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function $g$ of $n$ variables one can construct separating functions $g_1,\dots ,g_n$ in polynomial time with respect to the size of the input function.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G\left(1\right),\dots ,G\left(k\right)$. It is called an $r$-factorization if every $G\left(i\right)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1\le i\le k$, $G\left(i\right)$ is a subgraph of $H\left(i\right)$.Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some 2-edge-connected $r$-factorization of $\mu K_m$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu >\lambda$ and either $m\ge 2n?1$, or $m=2n?2$ and $\mu =2$ and $\lambda =1$, or $n=3$ and $m=4$. We generalize their result to every $r\ge 2$ and $m\ge 2n?2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some 2-edge-connected $r$-factorization of $\mu K_m$ for every $r\ge 3$ and $m>(2?C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and $\mu$.     

Spectral analysis of two doubly infinite Jacobi matrices with exponential entries

We provide a complete spectral analysis of all self-adjoint operators acting on ${?}^2(\mathbb{Z})$ which are associated with two doubly infinite Jacobi matrices with entries given by

$q^{?n+1}{\delta }_{m,n?1}+q^{?n}{\delta }_{m,n+1}$

and

${\delta }_{m,n?1}+\alpha q^{?n}{\delta }_{m,n}+{\delta }_{m,n+1},$

respectively, where $q\in (0,1)$ and $\alpha \in \mathbb{R}$. As an application, we derive orthogonality relations for the Ramanujan entire function and the third Jackson q-Bessel function.     

On the largest element in D(n)-quadruples

Let $n$ be a nonzero integer. A set of nonzero integers $\{a_1,\dots ,a_m\}$ such that $a_i{a}_j+n$ is a perfect square for all $1\le i<j\le m$ is called a $D\left(n\right)$-$m$-tuple. In this paper, we consider the question, for a given integer $n$ which is not a perfect square, how large and how small can be the largest element in a $D\left(n\right)$-quadruple. We construct families of $D\left(n\right)$-quadruples in which the largest element is of order of magnitude ${\left|n\right|}^3$, resp. ${\left|n\right|}^{2∕5}$.     

Analytic aspects of Delannoy numbers

The Delannoy numbers $d(n,k)$ count the number of lattice paths from $(0,0)$ to $(n?k,k)$ using steps $(1,0),(0,1)$ and $(1,1)$. We show that the zeros of all Delannoy polynomials $d_n\left(x\right)={\sum }_{k=0}^{n}d(n,k)x^k$ are in the open interval $(?3?2\sqrt{2},?3+2\sqrt{2})$ and are dense in the corresponding closed interval. We also show that the Delannoy numbers $d(n,k)$ are asymptotically normal (by central and local limit theorems).     

Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations

Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph $K_{2n}$, $n\ge 3$, which is properly colored with $2n?1$ colors, the edge set can be partitioned into $n$ edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every $2n\in \{2^s:s\ge 3\}\cup \{5?2^s,s\ge 1\}$ . Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of $K_{2n}$ constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine’s result also to all $2n\in \{2^{s}d:s\ge 1,d>3\text{odd}\}$.     

A generalization of Alon–Aydinian–Huang theorem

Let $S_{n,k}^m$ be the collection of sets of real numbers of size n, in which every subset of size larger than k has a sum less than m, where $n\ge k+1$, and m is some real number. Denote by $a_{n,k}^m$ the maximum number of nonempty subsets of a set in $S_{n,k}^m$ with a sum at least m. In particular, when $m=0$, Alon, Aydinian, Huang ((2014) [1]) proved that $a_{n,k}^0={\sum }_{i=0}^{k?1}\left(\begin{array}{c}n?1\\ i\end{array}\right)$, where two technical proofs, based on a weighted version of Hall's theorem and an extension of the nonuniform Erd?s–Ko–Rado theorem, were presented. In this note, we extend their elegant result from $m=0$ to any real number m, and show that $a_{n,k}^m=\{\begin{array}{cc}{\sum }_{i=0}^{k?1}\left(\begin{array}{c}n?1\\ i\end{array}\right)\hfill & \text{ if }m\ge 0\hfill \\ {\sum }_{i=1}^k\left(\begin{array}{c}n\\ i\end{array}\right)\hfill & \text{ if }m<0\hfill \end{array}$. Our proof is obtained by exploring the recurrence relation and initial conditions of $a_{n,k}^m$.     

No-three-in-line problem on a torus: Periodicity

Let ${\tau }_{m,n}$ denote the maximal number of points on the discrete torus (discrete toric grid) of sizes $m\times n$ with no three collinear points. The value ${\tau }_{m,n}$ is known for the case where $gcd(m,n)$ is prime. It is also known that ${\tau }_{m,n}\le 2gcd(m,n)$. In this paper we generalize some of the known tools for determining ${\tau }_{m,n}$ and also show some new. Using these tools we prove that the sequence ${\left({\tau }_{z,n}\right)}_{n\in \mathbb{N}}$ is periodic for all fixed $z>1$. In general, we do not know the period; however, if $z=p^a$ for $p$ prime, then we can bound it. We prove that ${\tau }_{p^a,p^{(a?1)p+2}}=2p^a$ which implies that the period for the sequence is $p^b$, where $b$ is at most $(a?1)p+2$.     

Ramsey number of multiple copies of stars

Let G and H be simple graphs. The Ramsey number $r(G,H)$ is the minimum integer N such that any red-blue-coloring of edges of $K_N$ contains either a red copy of G or a blue copy of H. Let $m{K}_{1,t}$ denote m vertex-disjoint copies of $K_{1,t}$. A lower bound is that $r(m{K}_{1,t},n{K}_{1,s})\ge m(t+1)+n?1$. Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t=s=3$, $m\ge 2$ and $m\ge n$. In this paper, we show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t\ge s=3,m\ge 2$ and $m\ge n$. We also show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $s\ge 4,t>\frac{s(s?1)}{2}$ and $m>n$.