On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

Congruences modulo powers of 3 for 3- and 9-colored generalized Frobenius partitions

Let $c{?}_k\left(n\right)$ be the number of $k$-colored generalized Frobenius partitions of $n$. We establish some infinite families of congruences for $c{?}_3\left(n\right)$ and $c{?}_9\left(n\right)$ modulo arbitrary powers of 3, which refine the results of Kolitsch. For example, for $k\ge 3$ and $n\ge 0$, we prove that

$c{?}_3\left(3^{2k}n+\frac{7?3^{2k}+1}{8}\right)\equiv 0(mod{3}^{4k+5}).$

We give two different proofs to the congruences satisfied by $c{?}_9\left(n\right)$. One of the proofs uses a relation between $c{?}_9\left(n\right)$ and $c{?}_3\left(n\right)$ due to Kolitsch, for which we provide a new proof in this paper.     

A note on rainbow matchings in strongly edge-colored graphs

The Ryser Conjecture which states that there is a transversal of size $n$ in a Latin square of odd order $n$ is equivalent to finding a rainbow matching of size $n$ in a properly edge-colored $K_{n,n}$ using $n$ colors when $n$ is odd. Let $\delta$ be the minimum degree of a graph. Wang proposed a more general question to find a function $f\left(\delta \right)$ such that every properly edge-colored graph of order $f\left(\delta \right)$ contains a rainbow matching of size $\delta$, which currently has the best bound of $f\left(\delta \right)\le 3.5\delta +2$ by Lo. Babu, Chandran and Vaidyanathan investigated Wang’s question under a stronger color condition. A strongly edge-colored graph is a properly edge-colored graph in which every monochromatic subgraph is an induced matching. Wang, Yan and Yu proved that every strongly edge-colored graph of order at least $2\delta +2$ has a rainbow matching of size $\delta$. In this note, we extend this result to graphs of order at least $2\delta +1$.     

Sums of powers of Catalan triangle numbers

In this paper, we consider combinatorial numbers ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$, mentioned as Catalan triangle numbers where $C_{m,k}?\left(\genfrac{}{}{0ex}{}{m?1}{k}\right)?\left(\genfrac{}{}{0ex}{}{m?1}{k?1}\right)$. These numbers unify the entries of the Catalan triangles $B_{n,k}$ and $A_{n,k}$ for appropriate values of parameters $m$ and $k$, i.e., $B_{n,k}=C_{2n,n?k}$ and $A_{n,k}=C_{2n+1,n+1?k}$. In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers $C_n$ that is $C_{2n,n?1}=C_{2n+1,n}=C_n$.We present identities for sums (and alternating sums) of $C_{m,k}$, squares and cubes of $C_{m,k}$ and, consequently, for $B_{n,k}$ and $A_{n,k}$. In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$ and harmonic numbers ${\left(H_n\right)}_{n\ge 1}$. Finally, in the last section, new open problems and identities involving ${\left(C_n\right)}_{n\ge 0}$ are conjectured.     

On topological and geometric (194) configurations

An $\left(n_k\right)$ configuration is a set of  $n$ points and  $n$ lines such that each point lies on  $k$ lines while each line contains  $k$ points. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines, or just combinatorial lines. The existence and enumeration of $\left(n_k\right)$ configurations for a given  $k$ has been subject to active research. A current front of research concerns geometric $\left(n_4\right)$ configurations: it is now known that geometric $\left(n_4\right)$ configurations exist for all  $n\ge 18$, apart from sporadic exceptional cases. In this paper, we settle by computational techniques the first open case of $\left(19_4\right)$ configurations: we obtain all topological $\left(19_4\right)$ configurations among which none are geometrically realizable.     

A degree sum condition for graphs to be covered by two cycles

Let $G$ be a $k$-connected graph of order $n$. In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if ${\sigma }_{k+1}\left(G\right)>(k+1)(n?1)/2$, then $G$ has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if $k=1$ and ${\sigma }_3\left(G\right)\ge n$, then $G$ can be covered by two cycles. By these results, we conjecture that if ${\sigma }_{2k+1}\left(G\right)>(2k+1)(n?1)/3$, then $G$ can be covered by two cycles. In this paper, we prove the case $k=2$ of this conjecture. In fact, we prove a stronger result; if $G$ is 2-connected with ${\sigma }_5\left(G\right)\ge 5(n?1)/3$, then $G$ can be covered by two cycles, or $G$ belongs to an exceptional class.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.     

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.     

Overpartition pairs modulo powers of 2

An overpartition of $n$ is a non-increasing sequence of positive integers whose sum is $n$ in which the first occurrence of a number may be overlined. In this article, we investigate the arithmetic behavior of $b_k\left(n\right)$ modulo powers of $2$, where $b_k\left(n\right)$ is the number of overpartition $k$-tuples of $n$. Using a combinatorial argument, we determine $b_2\left(n\right)$ modulo $8$. Employing the arithmetic of quadratic forms, we deduce that $b_2\left(n\right)$ is almost always divisible by $2^8$. Finally, with the aid of the theory of modular forms, for a fixed positive integer $j$, we show that $b_{2k}\left(n\right)$ is divisible by $2^j$ for almost all $n$.     

Sparse graphs of girth at least five are packable

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph $G$ with girth at least $5$ is packable.The conjecture was proved by Faudree et al. with the additional condition that $G$ has at most $\frac{6}{5}n?2$ edges. In this paper, for each integer $k\ge 3$, we prove that every non-star graph with girth at least $5$ and at most $\frac{2k?1}{k}n?{\alpha }_k\left(n\right)$ edges is packable, where ${\alpha }_k\left(n\right)$ is $o\left(n\right)$ for every $k$. This implies that the conjecture is true for sufficiently large planar graphs.     

On the distance between linear codes

Let V be an n-dimensional vector space over the finite field consisting of q elements and let ${\mathrm{\Gamma }}_k(V)$ be the Grassmann graph formed by k-dimensional subspaces of V, $1<k<n-1$. Denote by $\mathrm{\Gamma }{(n,k)}_q$ the restriction of ${\mathrm{\Gamma }}_k(V)$ to the set of all non-degenerate linear ${[n,k]}_q$ codes. We show that for any two codes the distance in $\mathrm{\Gamma }{(n,k)}_q$ coincides with the distance in ${\mathrm{\Gamma }}_k(V)$ only in the case when $n<{(q+1)}^2+k-2$, i.e. if n is sufficiently large then for some pairs of codes the distances in the graphs ${\mathrm{\Gamma }}_k(V)$ and $\mathrm{\Gamma }{(n,k)}_q$ are distinct. We describe one class of such pairs.     

The Laplacian spectral radius of trees and maximum vertex degree

Let $\Delta \left(T\right)$ and $\mu \left(T\right)$ denote the maximum degree and the Laplacian spectral radius of a tree $T$, respectively. In this paper we prove that for two trees $T_1$ and $T_2$ on $n(n\ge 21)$ vertices, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$, and the bound “$\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$” is the best possible. We also prove that for two trees $T_1$ and $T_2$ on $2k(k\ge 4)$ vertices with perfect matchings, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{k}{2}?+2$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$.     

Enumeration formulas for standard Young tableaux of nearly hollow rectangular shapes

This paper considers the enumeration problem of a generalization of standard Young tableau (SYT) of truncated shape. Let $\lambda ?\mu |\left\{(i_0,j_0)\right\}$ be the SYT of shape $\lambda$ truncated by $\mu$ whose upper left cell is $(i_0,j_0)$, where $\lambda$ and $\mu$ are partitions of integers. The summation representation of the number of SYT of the truncated shape $(n+k+2,{(n+2)}^{m+1})?\left(n^m\right)|\left\{(2,2)\right\}$ is derived. Consequently, three closed formulas for SYT of hollow shapes are obtained, including the cases of (i). $m=n=1$, (ii). $k=0$, and (iii). $k=1,m=n$. Finally, an open problem is posed.