Vertex-disjoint rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph of order $n$. The minimum color degree of $G$, denoted by ${\delta }^c\left(G\right)$, is the largest integer $k$ such that for every vertex $v$, there are at least $k$ distinct colors on edges incident to $v$. We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if ${\delta }^c\left(G\right)\ge (n+1)∕2$, then $G$ contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if $n\ge 20$ and ${\delta }^c\left(G\right)\ge (n+2)∕2$, then $G$ contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if ${\delta }^c\left(G\right)\ge (n+k)∕2$, then $G$ contains $k$ vertex-disjoint rainbow triangles. For any integer $k\ge 2$, we show that if $n\ge 16k-12$ and ${\delta }^c\left(G\right)\ge n∕2+k-1$, then $G$ contains $k$ vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of $k$ edge-disjoint rainbow triangles.     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).     

Construction of systematic (k + 1,k) memory MDS sliding window codes over embedded fields

In this paper, based on the structure of embedded fields, we investigate explicit construction of systematic $(k+1,k)$ mMDS sliding window codes with memory $m=2,3$. First, over GF($2^{lh}$) with $l\ge 1$ and $h\ge 2$, we propose an algorithm to construct $(2^{lh-1}+1,2^{lh-1})$ mMDS codes with memory 2, which are optimal in the sense that $2^{lh-1}$ is the maximum possible value of k for a $(k+1,k)$ sliding window code with memory 2 over GF($2^{lh}$) to be mMDS. When $l\ge 2$, every constructed code has the extra property that it contains a $(2^{h-1}+1,2^{h-1})$ mMDS sliding window code with memory 2 as a subcode over the subfield GF($2^h$). Next, over GF($2^{2lh}$) with $l\ge 1$ and $h\ge 2$, we introduce a method to construct $(k+1,k)$ mMDS codes memory 3, and a few new codes have been obtained consequently. When $l\ge 2$, every code constructed by the new approach also has the property that it contains an mMDS subcode over the subfield GF($2^{2h}$). The embedding subfield-subcode property enhances the flexibility and efficiency of the designed codes.     

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.     

On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

The space of lines in cyclic covers of projective space

Take positive integers m, n and d. Let Y be an m-fold cyclic cover of ${\mathbb{P}}^n$ ramified over a general hypersurface $X\subset P^n$ of degree md. In this paper we study the space $F(Y)$ of lines in Y and show that it is smooth of dimension $2(n-1)-d(m-1)$ if $md>2n-3$ and $2(n-1)-d(m-1)\ge 0$. When $2(n-1)=d(m-1)$, our result gives a formula on the number of m-contact order lines of X (see Definition 1.2).     

Irredundance trees of diameter 3

A set D of vertices of a graph $G=(V,E)$ is irredundant if each non-isolated vertex of $G[D]$ has a neighbour in $V?D$ that is not adjacent to any other vertex in D. The upper irredundance number $\mathrm{IR}(G)$ is the largest cardinality of an irredundant set of G; an $\mathrm{IR}(G)$-set is an irredundant set of cardinality $\mathrm{IR}(G)$.The IR-graph of G has the $\mathrm{IR}(G)$-sets as vertex set, and sets D and $D^{\prime }$ are adjacent if and only if $D^{\prime }$ can be obtained from D by exchanging a single vertex of D for an adjacent vertex in $D^{\prime }$. An IR-tree is an IR-graph that is a tree. We characterize IR-trees of diameter 3 by showing that these graphs are precisely the double stars $S(2n,2n)$, i.e., trees obtained by joining the central vertices of two disjoint stars $K_{1,2n}$.     

Cardinality constrained connected balanced partitions of trees under different criteria

In this paper we study the problem of partitioning a tree with $n$ weighted vertices into $p$ connected components. For each component, we measure its gap, that is, the difference between the maximum and the minimum weight of its vertices, with the aim of minimizing the sum of such differences. We present an $O\left(n^3{p}^2\right)$ time and $O\left(n^{3}p\right)$ space algorithm for this problem. Then, we generalize it, requiring a minimum of $ϵ\ge 1$ nodes in each connected component, and provide an $O\left(n^3{p}^2{ϵ}^2\right)$ time and $O\left(n^{3}pϵ\right)$ space algorithm to solve this new problem version. We provide a refinement of our analysis involving the topology of the tree and an improvement of the algorithms for the special case in which the weights of the vertices have a heap structure. All presented algorithms can be straightforwardly extended to other similar objective functions. Actually, for the problem of minimizing the maximum gap with a minimum number of nodes in each component, we propose an algorithm which is independent of $ϵ$ and requires $O(n^{2}logn{p}^2)$ time and $O\left(n^{2}p\right)$ space.     

Panchromatic 3-colorings of random hypergraphs

The paper deals with panchromatic 3-colorings of random hypergraphs. A vertex 3-coloring is said to be panchromatic for a hypergraph if every color can be found on every edge. Let $H(n,k,p)$ denote the binomial model of a random $k$-uniform hypergraph on $n$ vertices. For given fixed $c>0$, $k⩾3$ and $p=cn∕\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, we prove that if $c<\frac{ln3}{3}\cdot {\left(\frac{3}{2}\right)}^k-\frac{ln3}{2}-O\left({\left(\frac{\sqrt{3}}{2}\right)}^k\right)$then $H(n,k,p)$ admits a panchromatic 3-coloring with probability tending to 1 as $n\to \infty$, but if $k$ is large enough and $c>\frac{ln3}{3}\cdot {\left(\frac{3}{2}\right)}^k-\frac{ln3}{2}+O\left({\left(\frac{3}{4}\right)}^k\right)$then $H(n,k,p)$ does not admit a panchromatic 3-coloring with probability tending to 1 as $n\to \infty$.     

Some new results on dimension and Bose distance for various classes of BCH codes

In this paper, we give the dimension and the minimum distance of two subclasses of narrow-sense primitive BCH codes over ${\mathbb{F}}_q$ with designed distance $\delta =a{q}^{m-1}-1(\text{resp. }\delta =a\frac{q^m-1}{q-1})$ for all $1\le a\le q-1$, where q is a prime power and $m>1$ is a positive integer. As a consequence, we obtain an affirmative answer to two conjectures proposed by C. Ding in 2015. Furthermore, using the previous part, we extend some results of Yue and Hu [16], and we give the dimension and, in some cases, the Bose distance for a large designed distance in the range $[a\frac{q^m-1}{q-1},a\frac{q^m-1}{q-1}+T]$ for $0\le a\le q-2$, where $T=q^{\frac{m+1}{2}}-1$ if m is odd, and $T=2q^{\frac{m}{2}}-1$ if m is even.     

Classification of metabelian 2-groups G with Gab ≃ (2,2n),n ≥ 2, and rank d(G′)=2; Applications to real quadratic number fields

We characterize all finite metabelian 2-groups G whose abelianizations $G^{\mathrm{ab}}$ are of type $(2,2^n)$, with $n\ge 2$, and for which their commutator subgroups $G^{\prime }$ have $\text{rank}=2$. This is given in terms of the order of the abelianizations of the maximal subgroups and the structure of the abelianizations of those normal subgroups of index 4 in G. We then translate these group theoretic properties to give a characterization of number fields k with 2-class group ${\mathrm{Cl}}_2(k)?(2,2^n)$, $n\ge 2$, such that the rank of ${\mathrm{Cl}}_2(k^1)=2$ where $k^1$ is the Hilbert 2-class field of k. In particular, we apply all this to real quadratic number fields whose discriminants are a sum of two squares.     

A note on the distribution of weights of fixed-rank matrices over the binary field

Let M be a random $m\times n$ rank-r matrix over the binary field ${\mathbb{F}}_2$, and let $\mathrm{wt}(\mathbf{M})$ be its Hamming weight, that is, the number of nonzero entries of M.We prove that, as $m,n\to +\infty$ with r fixed and $m/n$ tending to a constant, we have that$\frac{\mathrm{wt}(\mathbf{M})-\frac{1-2^{-r}}{2}mn}{\sqrt{\frac{2^{-r}(1-2^{-r})}{4}(m+n)mn}}$ converges in distribution to a standard normal random variable.