Seminars in June 2019

  • Patrice Ossona de Mendez, A model theoretical approach to sparsity

    IBS/KAIST Joint Discrete Math Seminar

    A model theoretical approach to sparsity
    Patrice Ossona de Mendez
    CNRS, France
    2019/06/25 Tue 4:30PM-5:30PM
    We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.
    Tags:

  • Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues

    IBS/KAIST Joint Discrete Math Seminar

    An odd [1,b]-factor in regular graphs from eigenvalues
    Suil O (오수일)
    Department of Applied Mathematics and Statistics, SUNY-Korea
    2019/06/19 Wed 4:30PM-5:30PM
    An odd [1,b]-factor of a graph is a spanning subgraph H such that for every vertex v∈V(G), 1≤dH(v)≤b, and dH(v) is odd. For positive integers r≥3 and b≤r, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an r-regular graph with even number of vertices to guarantee the existence of an odd [1,b]-factor. In this talk, we improve their bound.
    Tags:

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

Monthly Archives