Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounterexamples on matchings in hypergraphs and full rainbow matchings in graphs
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 matchings in graphs, made by Aharoni and Berger and others.
rate research
Read More
There has been much research on the topic of finding a large rainbow matching (with no two edges having the same color) in a properly edge-colored graph, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barat, Gyarfas, and Sarkozy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed, but not loops) with $2q$ colors where each color appears at least $q$ times, there is always a rainbow matching of size $q$. Recently, Aharoni, Berger, Chudnovsky, Howard, and Seymour proved a relaxation of the conjecture with $3q-2$ colors. Our main result proves that $2q + o(q)$ colors are enough if the graph is simple, confirming the conjecture asymptotically for simple graphs. This question restricted to simple graphs was considered before by Aharoni and Berger. We also disprove one of their conjectures regarding the lower bound on the number of colors one needs in the conjecture of Barat, Gyarfas, and Sarkozy for the class of simple graphs. Our methods are inspired by the randomized algorithm proposed by Gao, Ramadurai, Wanless, and Wormald to find a rainbow matching of size $q$ in a graph that is properly edge-colored with $q$ colors, where each color class contains $q + o(q)$ edges. We consider a modified version of their algorithm, with which we are able to prove a generalization of their statement with a slightly better error term in $o(q)$. As a by-product of our techniques, we obtain a new asymptotic version of the Brualdi-Ryser-Stein Conjecture.
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 known 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 each $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)$.
A rainbow matching in an edge-colored graph is a matching in which no two edges have the same color. The color degree of a vertex v is the number of different colors on edges incident to v. Kritschgau [Electron. J. Combin. 27(2020)] studied the existence of rainbow matchings in edge-colored graph G with average color degree at least 2k, and proved some sufficient conditions for a rainbow marching of size k in G. The sufficient conditions include that |V(G)|>=12k^2+4k, or G is a properly edge-colored graph with |V(G)|>=8k. In this paper, we show that every edge-colored graph G with |V(G)|>=4k-4 and average color degree at least 2k-1 contains a rainbow matching of size k. In addition, we also prove that every strongly edge-colored graph G with average degree at least 2k-1 contains a rainbow matching of size at least k. The bound is sharp for complete graphs.
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 colors. 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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
