Degree anti-Ramsey numbers
Seminar
Speaker
Shoni Gilboa (Open University)
Date
23/12/2018 - 15:30 - 14:00Add to Calendar
2018-12-23 14:00:00
2018-12-23 15:30:00
Degree anti-Ramsey numbers
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.
Room 201, Math and CS Building (Bldg. 216)
אוניברסיטת בר-אילן - Department of Mathematics
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
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.
Last Updated Date : 17/12/2018
