Seminars in June 2018

  • Jinyoung Park (박진영), Coloring hypercubes
    Coloring hypercubes
    Jinyoung Park (박진영)
    Department of Mathematics, Rutgers, Piscataway, NJ, USA
    2018/06/26 Tuesday 5PM
    We discuss the number of proper colorings of hypercubes
    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.
    Tags:

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

    Intensive Lecture Series

    A course in graph embedding
    Jaehoon Kim (김재훈)
    School of Mathematics, Birmingham University, Birmingham, UK
    2018/6/25-29 10:30AM-12PM, 2:30PM-4PM (Room 3434, Bldg. E6-1)

    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

    Tags:

  • Eric Vigoda, Learning a graph via random colorings
    Learning a graph via random colorings
    Eric Vigoda
    College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
    2018/6/11 Mon 5PM-6PM
    For an unknown graph G on n vertices, given random k-colorings of G, can one learn the edges of G? We present results on identifiability/non-identifiability of the graph G and efficient algorithms for learning G. The results have interesting connections to statistical physics phase transitions.
    This is joint work with Antonio Blanca, Zongchen Chen, and Daniel Stefankovic.

Monthly Archives