Anti-Ramsey number of disjoint rainbow bases in all matroids

Publication date: 14 October 2021

Abstract: Consider a matroid

M = (E, m a t h c a l I)

with its elements of the ground set

E

colored. A rainbow basis is a maximum independent set in which each element receives a different color. The rank of a subset

S

of

E

, denoted by

r_{M} (S)

, is the maximum size of an independent set in

S

. A flat

F

is a maximal set in

M

with a fixed rank. The anti-Ramsey number of

t

pairwise disjoint rainbow bases in

M

, denoted by

a r (M, t)

, is defined as the maximum number of colors

m

such that there exists an

m

coloring of the ground set

E

of

M

which contains no

t

pairwise disjoint rainbow bases. We determine

a r (M, t)

for all matroids of rank at least 2:

a r (M, t) = | E |

if there exists a flat

F_{0}

with

| E | - | F_{0} | < t (r_{M} (E) - r_{M} (F_{0}))

; and

a r (M, t) = m a x_{F c o l o n r_{M} (F) l e q r_{M} (E) - 2} | F | + t (r_{M} (E) - r_{M} (F) - 1)

otherwise. This generalizes Lu-Meier-Wang's previous result on the anti-Ramsey number of edge-disjoint rainbow spanning trees in any multigraph

G

.

This page was built for publication: Anti-Ramsey number of disjoint rainbow bases in all matroids