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 Serre dimension of monoid algebras and Segre extensions

Let R be a commutative noetherian ring of dimension d and M be a commutative, cancellative, torsion-free monoid of rank r. Then S-$dim(R[M])\le max\{1,dim(R[M])?1\}$. Further, we define a class of monoids ${\{{\mathfrak{M}}_n\}}_{n\ge 1}$ such that if $M\in {\mathfrak{M}}_n$ is seminormal, then S-$dim(R[M])\le dim(R[M])?n=d+r?n$, where $1\le n\le r$. As an application, we prove that for the Segre extension $S_{mn}(R)$ over R, S-$dim(S_{mn}(R))\le dim(S_{mn}(R))?\left[\frac{m+n?1}{min\{m,n\}}\right]=d+m+n?1?\left[\frac{m+n?1}{min\{m,n\}}\right]$.     

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

Large blocking sets in PG(2,q2)

Minimal blocking sets in $\mathrm{PG}(2,q^2)$ have size at most $q^3+1$. This result is due to Bruen and Thas and the bound is sharp, sets attaining this bound are called unitals. In this paper, we show that the second largest minimal blocking sets have size at most $q^3+1-(p-3)/2$, if $q=p$, $p\ge 67$, or $q=p^h$, $p>7$, $h>1$. Our proof also works for sets having at least one tangent at each of its points (that is, for tangency sets).