Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs

DOI10.1137/22M1503178MaRDI QIDQ6046825zbMATH OpenFDO

Authors Mingyang Guo, Hongliang Lu, Xing Peng

Publication date 6 September 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.15631

anti-Ramsey number Erdős matching conjecture hypergraph rainbow matching

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05) Ramsey theory (05D10)

Abstract: Let

n, s,

and

k

be positive integers such that

k g e q 3

,

s g e q 3

and

n g e q k s

. An

s

-matching

M_{s}

in a

k

-uniform hypergraph is a set of

s

pairwise disjoint edges. The anti-Ramsey number

e x t r m a r (n, k, M_{s})

of an

s

-matching is the smallest integer

c

such that each edge-coloring of the

n

-vertex

k

-uniform complete hypergraph with exactly

c

colors contains an

s

-matching with distinct colors. In 2013, "Ozkahya and Young proposed a conjecture on the exact value of ar

(n, k, M_{s})

for all

n g e q s k

and

k g e q 3

. A 2019 result by Frankl and Kupavskii verified this conjecture for all

n g e q s k + (s - 1) (k - 1)

and

k g e q 3

. We aim to determine the value of ar

(n, 3, M_{s})

for

3 s l e q n < 5 s - 2

in this paper. Namely, we prove that if

3 s < n < 5 s - 2

and

n

is large enough, then ar

(n, 3, M_{s}) = e x t r m e x (n, 3, M_{s - 1}) + 2

. Here

e x t r m e x (n, 3, M_{s - 1})

is the Tur'an number of an

(s - 1)

-matching. Thus this result confirms the conjecture of "Ozkahya and Young for

k = 3

,

3 s < n < 5 s - 2

and sufficiently large

n

. For

n = k s

and

k g e q 3

, we present a new construction for the lower bound of

e x t r m a r (n, k, M_{s})

which shows the conjecture by "Ozkahya and Young is not true. In particular, for

n = 3 s

, we prove that

e x t r m a r (n, 3, M_{s}) = e x t r m e x (n, 3, M_{s - 1}) + 5

for sufficiently large

n

.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046825)