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.     

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.     

An upper bound on the number of frequency hypercubes

A frequency n-cube $F^n(q;l_0,...,l_{m-1})$ is an n-dimensional q-by-...-by-q array, where $q=l_0+...+l_{m-1}$, filled by numbers $0,...,m-1$ with the property that each line contains exactly $l_i$ cells with symbol i, $i=0,...,m-1$ (a line consists of q cells of the array differing in one coordinate). The trivial upper bound on the number of frequency n-cubes is $m^{{(q-1)}^n}$. We improve that lower bound for $n>2$, replacing $q-1$ by a smaller value s, by constructing a testing set of size $s^n$ for frequency n-cubes (a testing set is a collection of cells of an array the values in which uniquely determine the array with given parameters). We also construct new testing sets for generalized frequency n-cubes, which are essentially correlation-immune functions in n q-valued arguments; the cardinalities of new testing sets are smaller than for testing sets known before.     

On the Newton polygons of twisted L-functions of binomials

Let χ be an order c multiplicative character of a finite field and $f(x)=x^d+\lambda x^e$ a binomial with $(d,e)=1$. We study the twisted classical and T-adic Newton polygons of f. When $p>(d-e)(2d-1)$, we give a lower bound of Newton polygons and show that they coincide if p does not divide a certain integral constant depending on $p\mathrm{mod}cd$.We conjecture that this condition holds if p is large enough with respect to $c,d$ by combining all known results and the conjecture given by Zhang-Niu. As an example, we show that it holds for $e=d-1$.     

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

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