اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHamiltonian paths in m x n projective checkerboards
75
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For any two squares A and B of an m x n checkerboard, we determine whether it is possible to move a checker through a route that starts at A, ends at B, and visits each square of the board exactly once. Each step of the route moves to an adjacent square, either to the east or to the north, and may step off the edge of the board in a manner corresponding to the usual construction of a projective plane by applying a twist when gluing opposite sides of a rectangle. This generalizes work of M.H.Forbush et al. for the special case where m = n.
قيم البحث
اقرأ أيضاً
We provide a new geometric interpretation of the multidegrees of the (iterated) Kapranov embedding $Phi_n:overline{M}_{0,n+3}hookrightarrow mathbb{P}^1times mathbb{P}^2times cdots times mathbb{P}^n$, where $overline{M}_{0,n+3}$ is the moduli space of
stable genus $0$ curves with $n+3$ marked points. We enumerate the multidegrees by disjoint sets of boundary points of $overline{M}_{0,n+3}$ via a combinatorial algorithm on trivalent trees that we call a lazy tournament. These sets are compatible with the forgetting maps used to derive the recursion for the multidegrees proven in 2020 by Gillespie, Cavalieri, and Monin. The lazy tournament points are easily seen to total $(2n-1)!!=(2n-1)cdot (2n-3) cdots 5 cdot 3 cdot 1$, giving a natural proof of the fact that the total degree of $Phi_n$ is the odd double factorial. This fact was first proven using an insertion algorithm on certain parking functions, and we additionally give a bijection to those parking functions.
In 1999, Katona and Kierstead conjectured that if a $k$-uniform hypergraph $cal H$ on $n$ vertices has minimum co-degree $lfloor frac{n-k+3}{2}rfloor$, i.e., each set of $k-1$ vertices is contained in at least $lfloor frac{n-k+3}{2}rfloor$ edges, the
n it has a Hamiltonian cycle. R{o}dl, Ruci{n}ski and Szemer{e}di in 2011 proved that the conjecture is true when $k=3$ and $n$ is large. We show that this Katona-Kierstead conjecture holds if $k=4$, $n$ is large, and $V({cal H})$ has a partition $A$, $B$ such that $|A|=lceil n/2rceil$, $|{ein E({cal H}):|e cap A|=2}| <epsilon n^4$.
A set $X$ in the Euclidean space $mathbb{R}^d$ is called an $m$-distance set if the set of Euclidean distances between two distinct points in $X$ has size $m$. An $m$-distance set $X$ in $mathbb{R}^d$ is said to be maximal if there does not exist a v
ector $x$ in $mathbb{R}^d$ such that the union of $X$ and ${x}$ still has only $m$ distances. Bannai--Sato--Shigezumi (2012) investigated the maximal $m$-distance sets which contain the Euclidean representation of the Johnson graph $J(n,m)$. In this paper, we consider the same problem for the Hamming graph $H(n,m)$. The Euclidean representation of $H(n,m)$ is an $m$-distance set in $mathbb{R}^{m(n-1)}$. We prove that the maximum $n$ is $m^2 + m - 1$ such that the representation of $H(n,m)$ is not maximal as an $m$-distance set. Moreover we classify the largest $m$-distance sets which contain the representation of $H(n,m)$ for $mleq 4$ and any $n$. We also classify the maximal $2$-distance sets in $mathbb{R}^{2n-1}$ which contain the representation of $H(n,2)$ for any $n$.
In this paper, we present some new nonexistence results on $(m,n)$-generalized bent functions, which improved recent results. More precisely, we derive new nonexistence results for general $n$ and $m$ odd or $m equiv 2 pmod{4}$, and further explicitl
y prove nonexistence of $(m,3)$-generalized bent functions for all integers $m$ odd or $m equiv 2 pmod{4}$. The main tools we utilized are certain exponents of minimal vanishing sums from applying characters to group ring equations that characterize $(m,n)$-generalized bent functions.
We derive exactly the number of Hamiltonian paths H(n) on the two dimensional Sierpinski gasket SG(n) at stage $n$, whose asymptotic behavior is given by $frac{sqrt{3}(2sqrt{3})^{3^{n-1}}}{3} times (frac{5^2 times 7^2 times 17^2}{2^{12} times 3^5 tim
es 13})(16)^n$. We also obtain the number of Hamiltonian paths with one end at a certain outmost vertex of SG(n), with asymptotic behavior $frac {sqrt{3}(2sqrt{3})^{3^{n-1}}}{3} times (frac {7 times 17}{2^4 times 3^3})4^n$. The distribution of Hamiltonian paths on SG(n) with one end at a certain outmost vertex and the other end at an arbitrary vertex of SG(n) is investigated. We rigorously prove that the exponent for the mean $ell$ displacement between the two end vertices of such Hamiltonian paths on SG(n) is $ell log 2 / log 3$ for $ell>0$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
