اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCooperative conditions for the existence of rainbow matchings
362
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $k>1$, and let $mathcal{F}$ be a family of $2n+k-3$ non-empty sets of edges in a bipartite graph. If the union of every $k$ members of $mathcal{F}$ contains a matching of size $n$, then there exists an $mathcal{F}$-rainbow matching of size $n$. Upon replacing $2n+k-3$ by $2n+k-2$, the result can be proved both topologically and by a relatively simple combinatorial argument. The main effort is in gaining the last $1$, which makes the result sharp.
قيم البحث
اقرأ أيضاً
Drisko proved that $2n-1$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n$. For general graphs it is conjectured that $2n$ matchings suffice for this purpose (and that $2n-1$ matchings suffice when $n$ is even). The know
n graphs showing sharpness of this conjecture for $n$ even are called badges. We improve the previously best known bound from $3n-2$ to $3n-3$, using a new line of proof that involves analysis of the appearance of badges. We also prove a cooperative generalization: for $t>0$ and $n geq 3$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have a rainbow matching of size $n$.
Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number $mathfrak v = mathfrak v(n)$ such that, if $A_1, ldots, A_n$ are $n$ equivalence relations on a common finite ground set $X$, such that for ea
ch $i$ there are at least $mathfrak v$ elements of $X$ that belong to $A_i$-equivalence classes of size larger than $1$, then $X$ has a rainbow matching---a set of $2n$ distinct elements $a_1, b_1, ldots, a_n, b_n$, such that $a_i$ is $A_i$-equivalent to $b_i$ for each $i$? Grinblat has shown that $mathfrak v(n) le 10n/3 + O(sqrt{n})$. He asks whether $mathfrak v(n) = 3n-2$ for all $nge 4$. In this paper we improve the upper bound (for all large enough $n$) to $mathfrak v(n) le 16n/5 + O(1)$.
Given two graphs $G$ and $H$, the {it rainbow number} $rb(G,H)$ for $H$ with respect to $G$ is defined as the minimum number $k$ such that any $k$-edge-coloring of $G$ contains a rainbow $H$, i.e., a copy of $H$, all of its edges have different color
s. Denote by $M_t$ a matching of size $t$ and $mathcal {T}_n$ the class of all plane triangulations of order $n$, respectively. Jendrol, Schiermeyer and Tu initiated to investigate the rainbow numbers for matchings in plane triangulations, and proved some bounds for the value of $rb({mathcal {T}_n},M_t)$. Chen, Lan and Song proved that $2n+3t-14 le rb(mathcal {T}_n, M_t)le 2n+4t-13$ for all $nge 3t-6$ and $t ge 6$. In this paper, we determine the exact values of $rb({mathcal {T}_n},M_t)$ for large $n$, namely, $rb({mathcal {T}_n},M_t)=2n+3t-14$ for all $n ge 9t+3$ and $tge 7$.
Given two graphs $G$ and $H$, the {it rainbow number} $rb(G,H)$ for $H$ with respect to $G$ is defined as the minimum number $k$ such that any $k$-edge-coloring of $G$ contains a rainbow $H$, i.e., a copy of $H$, all of whose edges have different col
ors. Denote by $kK_2$ a matching of size $k$ and $mathcal {T}_n$ the class of all plane triangulations of order $n$, respectively. In [S. Jendrol$$, I. Schiermeyer and J. Tu, Rainbow numbers for matchings in plane triangulations, Discrete Math. 331(2014), 158--164], the authors determined the exact values of $rb(mathcal {T}_n, kK_2)$ for $2leq k le 4$ and proved that $2n+2k-9 le rb(mathcal {T}_n, kK_2) le 2n+2k-7+2binom{2k-2}{3}$ for $k ge 5$. In this paper, we improve the upper bounds and prove that $rb(mathcal {T}_n, kK_2)le 2n+6k-16$ for $n ge 2k$ and $kge 5$. Especially, we show that $rb(mathcal {T}_n, 5K_2)=2n+1$ for $n ge 11$.
A graph $G$ whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching $M$ that contains exactly one edge of each colour. We refute several conjectures on matchings in hypergraphs and full rainbow matc
hings in graphs, made by Aharoni and Berger and others.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
