Archive of posts with tag 'PatriceOssonadeMendez'

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

  • PatriceOssonadeMendez