Computer Science Department, Université Libre de Bruxelles, Brussels

## Archive for the ‘KAIST Discrete Math Seminar’ Category

### Tillmann Miltzow, The Art Gallery Problem is ∃R-complete

Tuesday, June 26th, 2018Computer Science Department, Université Libre de Bruxelles, Brussels

### (Intensive Lecture Series) Ron Aharoni, Lectures on topological methods in combinatorics

Wednesday, June 20th, 2018Intensive Lecture Series

Department of Mathematics, Technion, Israel

Topics that will be covered:

– A topological extension of Hall’s theorem

– combinatorial applications of the nerve theorem

– d-Leray complexes and rainbow matchings

– Matroid complexes and applications

– Open problems

### (Intensive Lecture Series) Jaehoon Kim, A course in graph embedding

Saturday, May 19th, 2018**Intensive Lecture Series**

School of Mathematics, Birmingham University, Birmingham, UK

In this lecture, we aim to learn several techniques to find sufficient conditions on a dense graph G to contain a sparse graph H as a subgraph.

Lecture note (PDF file)

**Tentative plan for the course (June 25, 26, 27, 28, 29)**

Lecture 1 : Basic probabilistic methods

Lecture 2 : Extremal number of graphs

Lecture 3 : Extremal number of even cycles

Lecture 4 : Dependent random choice

Lecture 5 : The regularity lemma and its applications

Lecture 6 : Embedding large graphs

Lecture 7 : The blow-up lemma and its applications I

Lecture 8 : The blow-up lemma and its applications II

Lecture 9 : The absorbing method I

Lecture 10 : The absorbing method II

### Jinyoung Park (박진영), Coloring hypercubes

Wednesday, May 16th, 2018Department of Mathematics, Rutgers, Piscataway, NJ, USA

given q colors. When q=2, it is easy to see that there are only 2

possible colorings. However, it is already highly nontrivial to figure

out the number of colorings when q=3. Since Galvin (2002) proved the

asymptotics of the number of 3-colorings, the rest cases remained open

so far. In this talk, I will introduce a recent work on the number of

4-colorings, mainly focusing on how entropy can be used in counting.

This is joint work with Jeff Kahn.

### Eric Vigoda, Learning a graph via random colorings

Tuesday, May 15th, 2018College of Computing, Georgia Institute of Technology, Atlanta, GA, USA

This is joint work with Antonio Blanca, Zongchen Chen, and Daniel Stefankovic.