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

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$.     

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.     

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.     

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$.