اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComplexity of Interlocking Polyominoes
89
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Polyominoes are a subset of polygons which can be constructed from integer-length squares fused at their edges. A system of polygons P is interlocked if no subset of the polygons in P can be removed arbitrarily far away from the rest. It is already known that polyominoes with four or fewer squares cannot interlock. It is also known that determining the interlockedness of polyominoes with an arbitrary number of squares is PSPACE hard. Here, we prove that a system of polyominoes with five or fewer squares cannot interlock, and that determining interlockedness of a system of polyominoes including hexominoes (polyominoes with six squares) or larger polyominoes is PSPACE hard.
قيم البحث
اقرأ أيضاً
We derive self-reciprocity properties for a number of polyomino generating functions, including several families of column-convex polygons, three-choice polygons and staircase polygons with a staircase hole. In so doing, we establish a connection bet
ween the reciprocity results known to combinatorialists and the inversion relations used by physicists to solve models in statistical mechanics. For several classes of convex polygons, the inversion (reciprocity) relation, augmented by certain symmetry and analyticity properties, completely determines the anisotropic perimeter generating function.
The main contribution of this paper is a new column-by-column method for the decomposition of generating functions of convex polyominoes suitable for enumeration with respect to various statistics including but not limited to interior vertices, bound
ary vertices of certain degrees, and outer site perimeter. Using this decomposition, among other things, we show that A) the average number of interior vertices over all convex polyominoes of perimeter $2n$ is asymptotic to $frac{n^2}{12}+frac{nsqrt{n}}{3sqrt{pi}} -frac{(21pi-16)n}{12pi}.$ B) the average number of boundary vertices with degree two over all convex polyominoes of perimeter $2n$ is asymptotic to $frac{n+6}{2}+frac{1}{sqrt{pi n}}+frac{(16-7pi)}{4pi n}.$ Additionally, we obtain an explicit generating function counting the number of convex polyominoes with $n$ boundary vertices of degrees at most three and show that this number is asymptotic to $ frac{n+1}{40}left(frac{3+sqrt{5}}{2}right)^{n-3} +frac{sqrt[4]{5}(2-sqrt{5})}{80sqrt{pi n}}left(frac{3+sqrt{5}}{2}right)^{n-2}. $ Moreover, we show that the expected number of the boundary vertices of degree four over all convex polyominoes with $n$ vertices of degrees at most three is asymptotically $ frac{n}{sqrt{5}}-frac{sqrt[4]{125}(sqrt{5}-1)sqrt{n}}{10sqrt{pi}}. $ C) the number of convex polyominoes with the outer-site perimeter $n$ is asymptotic to $frac{3(sqrt{5}-1)}{20sqrt{pi n}sqrt[4]{5}}left(frac{3+sqrt{5}}{2}right)^n,$ and show the expected number of the outer-site perimeter over all convex polyominoes with perimeter $2n$ is asymptotic to $frac{25n}{16}+frac{sqrt{n}}{4sqrt{pi}}+frac{1}{8}.$ Lastly, we prove that the expected perimeter over all convex polyominoes with the outer-site perimeter $n$ is asymptotic to $sqrt[4]{5}n$.
We define the Helly number of a polyomino $P$ as the smallest number $h$ such that the $h$-Helly property holds for the family of symmetric and translated copies of $P$ on the integer grid. We prove the following: (i) the only polyominoes with Helly
number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number $k$ for any $k eq 1,3$.
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called textit{codemaker} constructs a hidden sequence $H = (h_1, h_2, ldots, h_n)$ of colors selected from an alp
habet $mathcal{A} = {1,2,ldots, k}$ (textit{i.e.,} $h_iinmathcal{A}$ for all $iin{1,2,ldots, n}$). The game then proceeds in turns, each of which consists of two parts: in turn $t$, the second player (the textit{codebreaker}) first submits a query sequence $Q_t = (q_1, q_2, ldots, q_n)$ with $q_iin mathcal{A}$ for all $i$, and second receives feedback $Delta(Q_t, H)$, where $Delta$ is some agreed-upon function of distance between two sequences with $n$ components. The game terminates when $Q_t = H$, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let $f(n,k)$ denote the smallest integer such that the codebreaker can determine any $H$ in $f(n,k)$ turns. We prove three main results: First, when $H$ is known to be a permutation of ${1,2,ldots, n}$, we prove that $f(n, n)ge n - loglog n$ for all sufficiently large $n$. Second, we show that Knuths Minimax algorithm identifies any $H$ in at most $nk$ queries. Third, when feedback is not received until all queries have been submitted, we show that $f(n,k)=Omega(nlog k)$.
We introduce a notion of complexity for systems of linear forms called sequential Cauchy-Schwarz complexity, which is parametrized by two positive integers $k,ell$ and refines the notion of Cauchy-Schwarz complexity introduced by Green and Tao. We pr
ove that if a system of linear forms has sequential Cauchy-Schwarz complexity at most $(k,ell)$ then any average of 1-bounded functions over this system is controlled by the $2^{1-ell}$-th power of the Gowers $U^{k+1}$-norms of the functions. For $ell=1$ this agrees with Cauchy-Schwarz complexity, but for $ell>1$ there are families of systems that have sequential Cauchy-Schwarz complexity at most $(k,ell)$ whereas their Cauchy-Schwarz complexity is greater than $k$. For instance, for $p$ prime and $kin mathbb{N}$, the system of forms $big{phi_{z_1,z_2}(x,t_1,t_2)= x+z_1 t_1+z_2t_2;|; z_1,z_2in [0,p-1], z_1+z_2<kbig}$ can be viewed as a $2$-dimensional analogue of arithmetic progressions of length $k$. We prove that this system has sequential Cauchy-Schwarz complexity at most $(k-2,ell)$ for some $ell=O_{k,p}(1)$, even for $p<k$, whereas its Cauchy-Schwarz complexity can be strictly greater than $k-2$. In fact we prove this for the $M$-dimensional analogues of these systems for any $Mgeq 2$, obtaining polynomial true-complexity bounds for these and other families of systems. In a separate paper, we use these results to give a new proof of the inverse theorem for Gowers norms on vector spaces $mathbb{F}_p^n$, and applications concerning ergodic actions of $mathbb{F}_p^{omega}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
