اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Dichotomy Theorem for First-Fit Chain Partitions
62
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let $textrm{FF}(w,Q)$ be the maximum number of chains that First-Fit uses on a $Q$-free poset of width $w$. A result due to Bosek, Krawczyk, and Matecki states that $textrm{FF}(w,Q)$ is finite when $Q$ has width at most $2$. We describe a family of posets $mathcal{Q}$ and show that the following dichotomy holds: if $Qinmathcal{Q}$, then $textrm{FF}(w,Q) le 2^{c(log w)^2}$ for some constant $c$ depending only on $Q$, and if $Q otinmathcal{Q}$, then $textrm{FF}(w,Q) ge 2^w - 1$.
قيم البحث
اقرأ أيضاً
For an integer $mge 2$, a partition $lambda=(lambda_1,lambda_2,ldots)$ is called $m$-falling, a notion introduced by Keith, if the least nonnegative residues mod $m$ of $lambda_i$s form a nonincreasing sequence. We extend a bijection originally due t
o the third author to deduce a lecture hall theorem for such $m$-falling partitions. A special case of this result gives rise to a finite version of Pak-Postnikovs $(m,c)$-generalization of Eulers theorem. Our work is partially motivated by a recent extension of Eulers theorem for all moduli, due to Keith and Xiong. We note that their result actually can be refined with one more parameter.
This article is part of an ongoing investigation of the combinatorics of $q,t$-Catalan numbers $textrm{Cat}_n(q,t)$. We develop a structure theory for integer partitions based on the partition statistics dinv, deficit, and minimum triangle height. Ou
r goal is to decompose the infinite set of partitions of deficit $k$ into a disjoint union of chains $mathcal{C}_{mu}$ indexed by partitions of size $k$. Among other structural properties, these chains can be paired to give refinements of the famous symmetry property $textrm{Cat}_n(q,t)=textrm{Cat}_n(t,q)$. Previously, we introduced a map NU that builds the tail part of each chain $mathcal{C}_{mu}$. Our first main contribution here is to extend $NU$ and construct larger second-order tails for each chain. Second, we introduce new classes of partitions (flagpole partitions and generalized flagpole partitions) and give a recursive construction of the full chain $mathcal{C}_{mu}$ for generalized flagpole partitions $mu$.
A generalized crank ($k$-crank) for $k$-colored partitions is introduced. Following the work of Andrews-Lewis and Ji-Zhao, we derive two results for this newly defined $k$-crank. Namely, we first obtain some inequalities between the $k$-crank counts
$M_{k}(r,m,n)$ for $m=2,3$ and $4$, then we prove the positivity of symmetrized even $k$-crank moments weighted by the parity for $k=2$ and $3$. We conclude with several remarks on furthering the study initiated here.
We study two families of probability measures on integer partitions, which are Schur measures with parameters tuned in such a way that the edge fluctuations are characterized by a critical exponent different from the generic $1/3$. We find that the f
irst part asymptotically follows a higher-order analogue of the Tracy-Widom GUE distribution, previously encountered by Le Doussal, Majumdar and Schehr in quantum statistical physics. We also compute limit shapes, and discuss an exact mapping between one of our families and the multicritical unitary matrix models introduced by Periwal and Shevitz.
A seminal theorem of Tverberg states that any set of $T(r,d)=(r-1)(d+1)+1$ points in $mathbb{R}^d$ can be partitioned into $r$ subsets whose convex hulls have non-empty $r$-fold intersection. Almost any collection of fewer points in $mathbb{R}^d$ can
not be so divided, and in these cases we ask if the set can nonetheless be $P(r,d)$--partitioned, i.e., split into $r$ subsets so that there exist $r$ points, one from each resulting convex hull, which form the vertex set of a prescribed convex $d$--polytope $P(r,d)$. Our main theorem shows that this is the case for any generic $T(r,2)-2$ points in the plane and any $rgeq 3$ when $P(r,2)=P_r$ is a regular $r$--gon, and moreover that $T(r,2)-2$ is tight. For higher dimensional polytopes and $r=r_1cdots r_k$, $r_i geq 3$, this generalizes to $T(r,2k)-2k$ generic points in $mathbb{R}^{2k}$ and orthogonal products $P(r,2k)=P_{r_1}times cdots times P_{r_k}$ of regular polygons, and likewise to $T(2r,2k+1)-(2k+1)$ points in $mathbb{R}^{2k+1}$ and the product polytopes $P(2r,2k+1)=P_{r_1}times cdots times P_{r_k} times P_2$. As with Tverbergs original theorem, our results admit topological generalizations when $r$ is a prime power, and, using the constraint method of Blagojevic, Frick, and Ziegler, allow for dimensionally restrict
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
