Proof of a conjecture on monomial graphs

Let e be a positive integer, p be an odd prime, $q=p^e$, and ${\mathbb{F}}_q$ be the finite field of q elements. Let $f,g\in {\mathbb{F}}_q[X,Y]$. The graph $G_q(f,g)$ is a bipartite graph with vertex partitions $P={\mathbb{F}}_q^3$ and $L={\mathbb{F}}_q^3$, and edges defined as follows: a vertex $(p)=(p_1,p_2,p_3)\in P$ is adjacent to a vertex $[l]=[l_1,l_2,l_3]\in L$ if and only if $p_2+l_2=f(p_1,l_1)$ and $p_3+l_3=g(p_1,l_1)$. If $f=XY$ and $g=X{Y}^2$, the graph $G_q(XY,X{Y}^2)$ contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs $G_q(f,g)$ containing no cycles of length less than eight and not isomorphic to the graph $G_q(XY,X{Y}^2)$, even without requiring them to be edge-transitive. So far, no such graphs $G_q(f,g)$ have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture.     

A sharp Balian–Low uncertainty principle for shift-invariant spaces

A sharp version of the Balian–Low theorem is proven for the generators of finitely generated shift-invariant spaces. If generators ${\{f_k\}}_{k=1}^K?L^2({\mathbb{R}}^d)$ are translated along a lattice to form a frame or Riesz basis for a shift-invariant space V, and if V has extra invariance by a suitable finer lattice, then one of the generators $f_k$ must satisfy ${\int }_{{\mathbb{R}}^d}|x||f_k(x){|}^{2}dx=\infty$, namely, $\stackrel{?}{f_k}?H^{1/2}({\mathbb{R}}^d)$. Similar results are proven for frames of translates that are not Riesz bases without the assumption of extra lattice invariance. The best previously existing results in the literature give a notably weaker conclusion using the Sobolev space $H^{d/2+?}({\mathbb{R}}^d)$; our results provide an absolutely sharp improvement with $H^{1/2}({\mathbb{R}}^d)$. Our results are sharp in the sense that $H^{1/2}({\mathbb{R}}^d)$ cannot be replaced by $H^s({\mathbb{R}}^d)$ for any $s<1/2$.     

The mod 2 cohomology of the mapping class group of the Klein bottle with marked points

The purpose of this article is to compute the mod 2 cohomology of ${\mathrm{\Gamma }}^q(\mathbb{K})$, the mapping class group of the Klein bottle with q marked points. We provide a concrete construction of Eilenberg–MacLane spaces $X_q=K({\mathrm{\Gamma }}^q(\mathbb{K}),1)$ and fiber bundles $F_q(\mathbb{K})/{\mathrm{\Sigma }}_q\to X_q\to B({\mathbb{Z}}_2\times O(2))$, where $F_q(\mathbb{K})/{\mathrm{\Sigma }}_q$ denotes the configuration space of unordered q-tuples of distinct points in $\mathbb{K}$ and $B({\mathbb{Z}}_2\times O(2))$ is the classifying space of the group ${\mathbb{Z}}_2\times O(2)$. Moreover, we show the mod 2 Serre spectral sequence of the bundle above collapses.     

Construction of quasi-cyclic self-dual codes

There is a one-to-one correspondence between ?-quasi-cyclic codes over a finite field ${\mathbb{F}}_q$ and linear codes over a ring $R={\mathbb{F}}_q[Y]/(Y^m?1)$. Using this correspondence, we prove that every ?-quasi-cyclic self-dual code of length m? over a finite field ${\mathbb{F}}_q$ can be obtained by the building-up construction, provided that $\mathrm{char}({\mathbb{F}}_q)=2$ or $q\equiv 1(\mathrm{mod}4)$, m is a prime p, and q is a primitive element of ${\mathbb{F}}_p$. We determine possible weight enumerators of a binary ?-quasi-cyclic self-dual code of length p? (with p a prime) in terms of divisibility by p. We improve the result of Bonnecaze et al. (2003) [3] by constructing new binary cubic (i.e., ?-quasi-cyclic codes of length 3?) optimal self-dual codes of lengths $30,36,42,48$ (Type I), 54 and 66. We also find quasi-cyclic optimal self-dual codes of lengths 40, 50, and 60. When $m=5$, we obtain a new 8-quasi-cyclic self-dual $[40,20,12]$ code over ${\mathbb{F}}_3$ and a new 6-quasi-cyclic self-dual $[30,15,10]$ code over ${\mathbb{F}}_4$. When $m=7$, we find a new 4-quasi-cyclic self-dual $[28,14,9]$ code over ${\mathbb{F}}_4$ and a new 6-quasi-cyclic self-dual $[42,21,12]$ code over ${\mathbb{F}}_4$.