Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA combinatorial version of the colorful Caratheodory theorem
135
0
0.0
(
0
)
Authors
Andreas Holmsen
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 colorful 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 degree 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
