论文标题
部分可观测时空混沌系统的无模型预测
Girth of the algebraic bipartite graph $D(k,q)$
论文作者
论文摘要
对于Integer $ k \ geq2 $和Prime Power $ Q $，由Lazebnik和Ustimenko（1995）提出的代数二分$ D（K，Q）$不仅在极端图理论中有意义，而且在编码理论和密码学中也是有意义的。该图是$ q $ - 定型，边缘传递，至少$ k+4 $。 它的确切周长$ g = g（d（k，q））$在1995年被推测为$ k+5 $，对于奇数$ k $和$ q \ geq4 $。 当$ \ frac {k+5} {2} | _p（q-1）$时，该猜想在2016年有效，其中$ p $是$ \ m athbb {f} _q $和$ m | _pn $的特征，意味着$ m $ m $ p^r n $对于某些非norgation integer $ r r r n $。在本文中，对于$ t \ geq 1 $，我们证明（a）$ g（d（4t+2，q））= g（d（4t+1，q））$; （b）$ g（d（4t+3，q））= 4t+8 $如果$ g（d（2t，q））= 2t+4 $; （c）$ g（d（8t，q））= 8t+4 $如果$ g（d（4t-2，q））= 4t+2 $; （d）$ g（d（2^{s+2}（2t-1）-5，q））= 2^{s+2}（2t-1）$如果$ p \ geq 3 $，$（2T-1）| _p（q-1）$和$ 2^s \ s \ |（q-1）$。 本文末尾提出了$ d（k，q）$的简单上限。
For integer $k\geq2$ and prime power $q$, the algebraic bipartite graph $D(k,q)$ proposed by Lazebnik and Ustimenko (1995) is meaningful not only in extremal graph theory but also in coding theory and cryptography. This graph is $q$-regular, edge-transitive and of girth at least $k+4$. Its exact girth $g=g(D(k,q))$ was conjectured in 1995 to be $k+5$ for odd $k$ and $q\geq4$. This conjecture was shown to be valid in 2016 when $\frac{k+5}{2}|_p(q-1)$, where $p$ is the characteristic of $\mathbb{F}_q$ and $m|_pn$ means that $m$ divides $p^r n$ for some nonnegative integer $r$. In this paper, for $t\geq 1$ we prove that (a) $g(D(4t+2,q))=g(D(4t+1,q))$; (b) $g(D(4t+3,q))=4t+8$ if $g(D(2t,q))=2t+4$; (c) $g(D(8t,q))=8t+4$ if $g(D(4t-2,q))=4t+2$; (d) $g(D(2^{s+2}(2t-1)-5,q))=2^{s+2}(2t-1)$ if $p\geq 3$, $(2t-1)|_p(q-1)$ and $2^s\|(q-1)$. A simple upper bound for the girth of $D(k,q)$ is proposed in the end of this paper.
