Department Seminars & Colloquia
2023-10 | ||||||
---|---|---|---|---|---|---|
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 1 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
When you're logged in, you can subscribe seminars via e-mail
Room B332, IBS (기초과학연구원)
Discrete Mathematics
Domagoj Bradač (ETH Zürich)
Effective bounds for induced size-Ramsey numbers of cycles
Room B332, IBS (기초과학연구원)
Discrete Mathematics
The k-color induced size-Ramsey number of a graph H is the smallest number of edges a (host) graph G can have such that for any k-coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles these numbers are linear for any constant number of colours, i.e., for some C=C(k), there is a graph with at most Cn edges whose any k-edge-coloring contains a monochromatic induced cycle of length n. The value of C comes from the use of the sparse regularity lemma and has a tower-type dependence on k. In this work, we obtain nearly optimal bounds for the required value of C. Joint work with Nemanja Draganić and Benny Sudakov.