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.     

Nice derivations over principal ideal domains

In this paper we investigate to what extent the results of Z. Wang and D. Daigle on “nice derivations” of the polynomial ring $k[X,Y,Z]$ over a field k of characteristic zero extend to the polynomial ring $R[X,Y,Z]$ over a PID R, containing the field of rational numbers. One of our results shows that the kernel of a nice derivation on $k[X_1,X_2,X_3,X_4]$ of rank at most three is a polynomial ring over k.     

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

Lower bounds for moments of global scores of pairwise Markov chains

Let $X_1,\dots$ and $Y_1,\dots$ be random sequences taking values in a finite set $\mathbb{A}$. We consider a similarity score $L_n?L(X_1,\dots ,X_n;Y_1,\dots ,Y_n)$ that measures the homology of words $(X_1,\dots ,X_n)$ and $(Y_1,\dots ,Y_n)$. A typical example is the length of the longest common subsequence. We study the order of moment $E{|L_n?E{L}_n|}^r$ in the case where the two-dimensional process $(X_1,Y_1),(X_2,Y_2),\dots$ is a Markov chain on $\mathbb{A}\times \mathbb{A}$. This general model involves independent Markov chains, hidden Markov models, Markov switching models and many more. Our main result establishes a condition that guarantees that $E{|L_n?E{L}_n|}^r?n^{\frac{r}{2}}$. We also perform simulations indicating the validity of the condition.     

On the longest common increasing binary subsequence

Let $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ be two independent sequences of iid Bernoulli random variables with parameter 1/2. Let ${\mathit{LCI}}_n$ be the length of the longest increasing sequence which is a subsequence of both finite sequences $X_1,\dots ,X_n$ and $Y_1,\dots ,Y_n$. We prove that, as n goes to infinity, $n^{?1/2}({\mathit{LCI}}_n?n/2)$ converges in law to a Brownian functional that we identify. To cite this article: C. Houdré et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Approximation of maximum of Gaussian random fields

This contribution is concerned with Gumbel limiting results for supremum ${\mathbb{M}}_{\mathit{n}}={\sup }_{\mathit{t}\in [\mathbf{0},{\mathit{T}}_{\mathit{n}}]}?|X_{\mathit{n}}(\mathit{t})|$ with $X_{\mathit{n}},\mathit{n}\in {\mathbb{N}}^2$ centered Gaussian random fields with continuous trajectories. We show first the convergence of a related point process to a Poisson point process thereby extending previous results obtained in [8] for Gaussian processes. Furthermore, we derive Gumbel limit results for ${\mathbb{M}}_{\mathit{n}}$ as $\mathit{n}\to \infty$ and show a second-order approximation for $\mathbb{E}{\{{\mathbb{M}}_{\mathit{n}}^p\}}^{1/p}$ for any $p\ge 1$.     

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.     

On Noether's problem for central extensions of symmetric and alternating groups

For a field k and a finite group G acting regularly on a set of indeterminates $\underset{?}{X}={\{X_g\}}_{g\in G}$, let $k(G)$ denote the invariant field $k{(\underset{?}{X})}^G$. We first prove for the alternating group $A_n$ that, if n is odd, then $\mathbb{Q}(A_n)$ is rational over $\mathbb{Q}(A_{n?1})$. We then obtain an analogous result where $A_n$ is replaced by an arbitrary finite central extension of either $A_n$ or $S_n$, valid over $\mathbb{Q}({\zeta }_N)$ for suitable N. Concrete applications of our results yield: (1) a new proof of Maeda's result on the rationality of $\mathbb{Q}{(X_1,\dots ,X_5)}^{A_5}/\mathbb{Q}$; (2) an affirmative answer to Noether's problem over $\mathbb{Q}$ for both $\stackrel{?}{A_5}$ and $\stackrel{?}{S_5}$; (3) an affirmative answer to Noether's problem over $\mathbb{C}$ for every finite central extension group of either $A_n$ or $S_n$ with $n?5$.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.     

Non-level semi-standard graded Cohen–Macaulay domain with h-vector (h0,h1,h2)

Let $\mathbb{k}$ be an algebraically closed field of characteristic 0, and $A={?}_{i\in \mathbb{N}}{A}_i$ a Cohen–Macaulay graded domain with $A_0=\mathbb{k}$. If A is semi-standard graded (i.e., A is finitely generated as a $\mathbb{k}[A_1]$-module), it has the h-vector$(h_0,h_1,\dots ,h_s)$, which encodes the Hilbert function of A. From now on, assume that $s=2$. It is known that if A is standard graded (i.e., $A=\mathbb{k}[A_1]$), then A is level. We will show that, in the semi-standard case, if A is not level, then $h_1+1$ divides $h_2$. Conversely, for any positive integers h and n, there is a non-level A with the h-vector $(1,h,(h+1)n)$. Moreover, such examples can be constructed as Ehrhart rings (equivalently, normal toric rings).     

Y spaces and global smooth solution of fractional Navier–Stokes equations with initial value in the critical oscillation spaces

For fractional Navier–Stokes equations and critical initial spaces X, one used to establish the well-posedness in the solution space which is contained in $C({\mathbb{R}}_{+},X)$. In this paper, for heat flow, we apply parameter Meyer wavelets to introduce Y spaces $Y^{m,\beta }$ where $Y^{m,\beta }$ is not contained in $C({\mathbb{R}}_{+},{\dot{B}}_{\infty }^{1?2\beta ,\infty })$. Consequently, for $\frac{1}{2}<\beta <1$, we establish the global well-posedness of fractional Navier–Stokes equations with small initial data in all the critical oscillation spaces. The critical oscillation spaces may be any Besov–Morrey spaces ${({\dot{B}}_{p,q}^{{\gamma }_1,{\gamma }_2}({\mathbb{R}}^n))}^n$ or any Triebel–Lizorkin–Morrey spaces ${({\dot{F}}_{p,q}^{{\gamma }_1,{\gamma }_2}({\mathbb{R}}^n))}^n$ where $1\le p,q\le \infty ,0\le {\gamma }_2\le \frac{n}{p},{\gamma }_1?{\gamma }_2=1?2\beta$. These critical spaces include many known spaces. For example, Besov spaces, Sobolev spaces, Bloch spaces, Q-spaces, Morrey spaces and Triebel–Lizorkin spaces etc.