박진영

Archive of posts with tag '박진영'

  • Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

    IBS/KAIST Joint Discrete Math Seminar

    The number of maximal independent sets in the Hamming cube
    Jinyoung Park (박진영)
    Department of Mathematics, Rutgers University, USA
    2019/06/03 Monday 4:30PM-5:30PM (IBS, Room B232)
    Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn.
    Tags:

  • 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:

Monthly Archives