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.     

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

Path decompositions of triangle-free graphs

Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then $p(G)\le ?n/2?$. If G is allowed to be disconnected, then the upper bound $?\frac{3}{4}n?$ for $p(G)$ was obtained by Donald [7], which was improved to $?\frac{2}{3}n?$ independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, $?\frac{2}{3}n?$ is reached and so this bound is tight. If triangles are forbidden in G, then $p(G)\le ?\frac{g+1}{2g}n?$ can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that $p(G)\le ?3n/5?$, which improves the above result with $g=4$.     

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

A characterization of graphs with given maximum degree and smallest possible matching number: II

Let ${\alpha }^{\prime }(G)$ be the matching number of a graph G. A characterization of the graphs with given maximum odd degree and smallest possible matching number is given by Henning and Shozi (2021) [13]. In this paper we complete our study by giving a characterization of the graphs with given maximum even degree and smallest possible matching number. In 2018 Henning and Yeo [10] proved that if G is a connected graph of order n, size m and maximum degree k where $k\ge 4$ is even, then ${\alpha }^{\prime }(G)\ge \frac{n}{k(k+1)}+\frac{m}{k+1}?\frac{1}{k(k+1)}$, unless G is k-regular and $n\in \{k+1,k+3\}$. In this paper, we give a complete characterization of the graphs that achieve equality in this bound when the maximum degree k is even, thereby completing our study of graphs with given maximum degree and smallest possible matching number.     

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.     

An infinite family of m-ovoids of Q(4,q)

In this paper, we construct an infinite family of $\frac{q-1}{2}$-ovoids of the generalized quadrangle $Q(4,q)$, for $q\equiv 1(\text{mod}4)$ and $q>5$. Together with [3] and [11], this establishes the existence of $\frac{q-1}{2}$-ovoids in $Q(4,q)$ for each odd prime power q.     

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

On eigenfunctions and maximal cliques of generalised Paley graphs of square order

Let GP $(q^2,m)$ be the m-Paley graph defined on the finite field with order $q^2$. We study eigenfunctions and maximal cliques in generalised Paley graphs GP $(q^2,m)$, where $m|(q+1)$. In particular, we explicitly construct maximal cliques of size $\frac{q+1}{m}$ or $\frac{q+1}{m}+1$ in GP $(q^2,m)$, and show the weight-distribution bound on the cardinality of the support of an eigenfunction is tight for the smallest eigenvalue $-\frac{q+1}{m}$ of GP $(q^2,m)$. These new results extend the work of Baker et al. and Goryainov et al. on Paley graphs of square order. We also study the stability of the Erdős-Ko-Rado theorem for GP $(q^2,m)$ (first proved by Sziklai).