اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA combinatorial version of the colorful Caratheodory theorem
139
0
0.0
(
0
)
تأليف
Andreas Holmsen
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We give the following extension of Baranys colorful Caratheodory theorem: Let M be an oriented matroid and N a matroid with rank function r, both defined on the same ground set V and satisfying rank(M) < rank(N). If every subset A of V with r(V - A) < rank (M) contains a positive circuit of M, then some independent set of N contains a positive circuit of M.
قيم البحث
اقرأ أيضاً
Hellys theorem is a classical result concerning the intersection patterns of convex sets in $mathbb{R}^d$. Two important generalizations are the colorful version and the fractional version. Recently, B{a}r{a}ny et al. combined the two, obtaining a co
lorful fractional Helly theorem. In this paper, we give an improved version of their result.
For a collection $mathbf{G}={G_1,dots, G_s}$ of not necessarily distinct graphs on the same vertex set $V$, a graph $H$ with vertices in $V$ is a $mathbf{G}$-transversal if there exists a bijection $phi:E(H)rightarrow [s]$ such that $ein E(G_{phi(e)}
)$ for all $ein E(H)$. We prove that for $|V|=sgeq 3$ and $delta(G_i)geq s/2$ for each $iin [s]$, there exists a $mathbf{G}$-transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.
Caratheodory showed that $n$ complex numbers $c_1,...,c_n$ can uniquely be written in the form $c_p=sum_{j=1}^m rho_j {epsilon_j}^p$ with $p=1,...,n$, where the $epsilon_j$s are different unimodular complex numbers, the $rho_j$s are strictly positive
numbers and integer $m$ never exceeds $n$. We give the conditions to be obeyed for the former property to hold true if the $rho_j$s are simply required to be real and different from zero. It turns out that the number of the possible choices of the signs of the $rho_j$s are {at most} equal to the number of the different eigenvalues of the Hermitian Toeplitz matrix whose $i,j$-th entry is $c_{j-i}$, where $c_{-p}$ is equal to the complex conjugate of $c_{p}$ and $c_{0}=0$. This generalization is relevant for neutron scattering. Its proof is made possible by a lemma - which is an interesting side result - that establishes a necessary and sufficient condition for the unimodularity of the roots of a polynomial based only on the polynomial coefficients. Keywords: Toeplitz matrix factorization, unimodular roots, neutron scattering, signal theory, inverse problems. PACS: 61.12.Bt, 02.30.Zz, 89.70.+c, 02.10.Yn, 02.50.Ga
A fundamental result of Kuhn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009] determines up to an additive constant the minimum degree threshold that forces a graph to contain a perfect H-tiling. We prove a de
gree sequence version of this result which allows for a significant number of vertices to have lower degree.
We study the finite dimensional partition properties of the countable homogeneous dense local order. Some of our results use ideas borrowed from the partition calculus of the rationals and are obtained thanks to a strengthening of Millikens theorem on trees.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
