اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMinimum size generating partitions and their application to demand fulfillment optimization problems
88
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For $n$ and $k$ integers we introduce the notion of some partition of $n$ being able to generate another partition of $n$. We solve the problem of finding the minimum size partition for which the set of partitions this partition can generate contains all size-$k$ partitions of $n$. We describe how this result can be applied to solving a class of combinatorial optimization problems.
قيم البحث
اقرأ أيضاً
Johnson recently proved Armstrongs conjecture which states that the average size of an $(a,b)$-core partition is $(a+b+1)(a-1)(b-1)/24$. He used various coordinate changes and one-to-one correspondences that are useful for counting problems about sim
ultaneous core partitions. We give an expression for the number of $(b_1,b_2,cdots, b_n)$-core partitions where ${b_1,b_2,cdots,b_n}$ contains at least one pair of relatively prime numbers. We also evaluate the largest size of a self-conjugate $(s,s+1,s+2)$-core partition.
We study plane partitions satisfying condition $a_{n+1,m+1}=0$ (this condition is called pit) and asymptotic conditions along three coordinate axes. We find the formulas for generating function of such plane partitions. Such plane partitions label
the basis vectors in certain representations of quantum toroidal $mathfrak{gl}_1$ algebra, therefore our formulas can be interpreted as the characters of these representations. The resulting formulas resemble formulas for characters of tensor representations of Lie superalgebra $mathfrak{gl}_{m|n}$. We discuss representation theoretic interpretation of our formulas using $q$-deformed $W$-algebra $mathfrak{gl}_{m|n}$.
The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity / minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph o
f order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z_+(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented.
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polyn
omially-related Kolmogorov measure. All prior reductions from supposedly-intractable problems to MCSP / MKTP hinged on the power of MCSP / MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of Graph Isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include Linear Code Equivalence, Permutation Group Conjugacy, and Matrix Subspace Conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.
For non-negative integers $n$ and $k$ with $n ge k$, a {em $k$-minor} of a partition $lambda = [lambda_1, lambda_2, dots]$ of $n$ is a partition $mu = [mu_1, mu_2, dots]$ of $n-k$ such that $mu_i le lambda_i$ for all $i$. The multiset $widehat{M}_k(l
ambda)$ of $k$-minors of $lambda$ is defined as the multiset of $k$-minors $mu$ with multiplicity of $mu$ equal to the number of standard Young tableaux of skew shape $lambda / mu$. We show that there exists a function $G(n)$ such that the partitions of $n$ can be reconstructed from their multisets of $k$-minors if and only if $k le G(n)$. Furthermore, we prove that $lim_{n rightarrow infty} G(n)/n = 1$ with $n-G(n) = O(n/log n)$. As a direct consequence of this result, the irreducible representations of the symmetric group $S_n$ can be reconstructed from their restrictions to $S_{n-k}$ if and only if $k le G(n)$ for the same function $G(n)$. For a minor $mu$ of the partition $lambda$, we study the excitation factor $E_mu (lambda)$, which appears as a crucial part in Naruses Skew-Shape Hook Length Formula. We observe that certain excitation factors of $lambda$ can be expressed as a $mathbb{Q}[k]$-linear combination of the elementary symmetric polynomials of the hook lengths in the first row of $lambda$ where $k = lambda_1$ is the number of cells in the first row of $lambda$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
