Remarks on the distribution of colors in Gallai colorings

A Gallai coloring of a complete graph $K_n$ is an edge coloring without triangles colored with three different colors. A sequence $e_1\ge \cdots \ge e_k$ of positive integers is an $(n,k)$-sequence if ${\sum }_{i=1}^k{e}_i=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. An $(n,k)$-sequence is a G-sequence if there is a Gallai coloring of $K_n$ with $k$ colors such that there are $e_i$ edges of color $i$ for all $i,1\le i\le k$. Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer $k\ge 3$ there exists an integer $g\left(k\right)$ such that every $(n,k)$-sequence is a G-sequence if and only if $n\ge g\left(k\right)$. They showed that $g\left(3\right)=5,g\left(4\right)=8$ and $2k-2\le g\left(k\right)\le 8k^2+1$.We show that $g\left(5\right)=10$ and give almost matching lower and upper bounds for $g\left(k\right)$ by showing that with suitable constants $\alpha ,\beta >0$, $\frac{\alpha k^{1.5}}{lnk}\le g\left(k\right)\le \beta k^{1.5}$ for all sufficiently large $k$.     

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.     

Erdős matching conjecture for almost perfect matchings

In 1965 Erd?s asked, what is the largest size of a family of k-element subsets of an n-element set that does not contain a matching of size $s+1$? In this note, we improve upon a recent result of Frankl and resolve this problem for $s>101k^3$ and $(s+1)k?n<(s+1)(k+\frac{1}{100k})$.     

Bounds for moments of cubic and quartic Dirichlet L-functions

We study the $2k$-th moment of central values of the family of primitive cubic and quartic Dirichlet $L$-functions. We establish sharp lower bounds for all real $k\ge 1/2$ unconditionally for the cubic case and under the Lindelöf hypothesis for the quartic case. We also establish sharp lower bounds for all real $0\le k<1/2$ and sharp upper bounds for all real $k\ge 0$ for both the cubic and quartic cases under the generalized Riemann hypothesis (GRH). As an application of our results, we establish quantitative non-vanishing results for the corresponding $L$-values.     

Note on rainbow cycles in edge-colored graphs

Let G be a graph of order n with an edge-coloring c, and let ${\delta }^c(G)$ denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if ${\delta }^c(G)>\frac{2n?1}{3}$, then every vertex of G is contained in a rainbow triangle; (ii) if ${\delta }^c(G)>\frac{2n?1}{3}$ and $n\ge 13$, then every vertex of G is contained in a rainbow $C_4$; (iii) if G is complete, $n\ge 7k?17$ and ${\delta }^c(G)>\frac{n?1}{2}+k$, then G contains a rainbow cycle of length at least k, where $k\ge 5$.     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

Dynamical behavior of solutions of a reaction–diffusion model in river network

In this paper, we study the long-time behavior of solutions of a reaction–diffusion model in a one-dimensional river network, where the river network has two branches, and the water flow speeds in each branch are the same constant $\beta$. We show the existence of two critical values $c_0$ and 2 with $0<c_0<2$, and prove that when $-c_0\le \beta <2$, the population density in every branch of the river goes to 1 as time goes to infinity; when $-2<\beta <-c_0$, then, as time goes to infinity, the population density in every river branch converges to a positive steady state strictly below 1; when $\left|\beta \right|\ge 2$, the species will be washed down the stream, and so locally the population density converges to 0. Our result indicates that only if the water-flow speed is suitably small (i.e., $\left|\beta \right|<2$), the species will survive in the long run.     

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.     

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.     

On the size of special class 1 graphs and (P3;k)-co-critical graphs

A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index ${\chi }^{\prime }(G)$ of G is Δ or $\mathrm{\Delta }+1$. A graph G is class 1 if ${\chi }^{\prime }(G)=\mathrm{\Delta }$, and class 2 if ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$; G is Δ-critical if it is connected, class 2 and ${\chi }^{\prime }(G-e)<{\chi }^{\prime }(G)$ for every $e\in E(G)$. A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least $(n(\mathrm{\Delta }-1)+3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, ${\chi }^{\prime }(G+e)={\chi }^{\prime }(G)+1$ for every $e\in E(\bar{G})$. Such graphs have intimate relation to $(P_3;k)$-co-critical graphs, where a non-complete graph G is $(P_3;k)$-co-critical if there exists a k-coloring of $E(G)$ such that G does not contain a monochromatic copy of $P_3$ but every k-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in E(\bar{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3;k)$-co-critical graphs. We prove that if G is a $(P_3;k)$-co-critical graph on $n\ge k+2$ vertices, then$e(G)\ge \frac{k}{2}(n-\lceil \frac{k}{2}\rceil -\epsilon )+\left(\begin{array}{c}\lceil k/2\rceil +\epsilon \\ 2\end{array}\right),$ where ε is the remainder of $n-\lceil k/2\rceil$ when divided by 2. This bound is best possible for all $k\ge 1$ and $n\ge \lceil 3k/2\rceil +2$.