שלחו לחבר

Degree anti-Ramsey numbers

Seminar
Speaker
Shoni Gilboa (Open University)
Date
23/12/2018 - 15:30 - 14:00
Place
Room 201, Math and CS Building (Bldg. 216)
Abstract

The degree anti-Ramsey number of a graph H is the smallest integer k for which there exists a graph G with maximum degree at most k such that any proper edge colouring of G yields a rainbow copy of H (i.e., all edges of this copy of H have distinct colours).

We determine the degree anti-Ramsey number of any tree, and then extend this to any forest using a classical result of Bollobas concerning cross intersecting families. We also use a topological version of Hall's Theorem due to Aharoni, Berger and Meshulam to get an upper bound (which is best possible up to a factor of 2) on the degree anti-Ramsey numbers of cycles of any length, .

Joint work with Danny Hefetz.

תאריך עדכון אחרון : 17/12/2018