Document Open Access Logo

First-Order Transductions of Graphs (Invited Talk)

Author Patrice Ossona de Mendez

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.2.pdf
  • Filesize: 0.66 MB
  • 7 pages

Document Identifiers

Author Details

Patrice Ossona de Mendez
  • Centre d'Analyse et de Mathématique Sociales CNRS UMR 8557, Paris, France
  • Charles University, Prague, Czech Republic

Funding

This paper is part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 810115 - Dynasnet).

Acknowledgements

I would like to thank Jarik Nešetřil and Sebastian Siebertz for their most valuable help in preparing this presentation.

Cite As Get BibTex

Patrice Ossona de Mendez. First-Order Transductions of Graphs (Invited Talk). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 2:1-2:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.2

Abstract

This paper is an extended abstract of my STACS 2021 talk "First-order transductions of graphs".

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Mathematics of computing → Graph theory
Keywords
  • Finite model theory
  • structural graph theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Adler. An introduction to theories without the independence property. preprint, 2008. URL: http://www.logic.univie.ac.at/~adler/docs/nip.pdf.
  2. H. Adler and I. Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322-330, 2014. URL: https://doi.org/10.1016/j.ejc.2013.06.048.
  3. J.T. Baldwin and S. Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229-303, 1985. Google Scholar
  4. E. Bonnet, C. Geniet, E.J. Kim, S. Thomassé, and R. Watrigant. Twin-width II: small classes. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1977-1996, 2021. URL: https://doi.org/10.1137/1.9781611976465.118.
  5. E. Bonnet, U. Giocanti, S. Thomassé, and P. Ossona de Mendez. Twin-width IV: low complexity matrices. in preparation, 2021. Google Scholar
  6. E. Bonnet, E.J. Kim, S. Thomassé, and R. Watrigant. Twin-width I: tractable FO model checking. CoRR, abs/2004.14789, 2020, To appear at FOCS 2020. URL: http://arxiv.org/abs/2004.14789.
  7. A. Dawar. Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences, 76:324-332, 2010. URL: https://doi.org/10.1016/j.jcss.2009.10.005.
  8. Z. Dvořák. On forbidden subdivision characterizations of graph classes. European Journal of Combinatorics, 29(5):1321-1332, 2008. URL: https://doi.org/10.1016/j.ejc.2007.05.008.
  9. Z. Dvořák. A stronger structure theorem for excluded topological minors, 2012. URL: http://arxiv.org/abs/1209.0129v1.
  10. Z. Dvořák, P. Ossona de Mendez, and H. Wu. 1-subdivisions, fractional chromatic number and Hall ratio. Combinatorica, 2020. to appear. URL: https://doi.org/10.1007/s00493-020-4223-9.
  11. K. Eickmeyer, A. C Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.63.
  12. J. Gajarský, P. Hliněný, J. Obdržálek, D. Lokshtanov, and M.S. Ramanujan. A new perspective on FO model checking of dense graph classes. In Proceedings of the Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 176-184. ACM, 2016. URL: https://doi.org/10.1145/3383206.
  13. J. Gajarsky, P. Hliněny, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F.S. Villaamil, and S. Sikdar. Kernelization using structural parameters on sparse graph classes. Journal of Computer and System Sciences, 84:219-242, 2017. URL: https://doi.org/10.1016/j.jcss.2016.09.002.
  14. J. Gajarský and D. Kráľ. Recovering sparse graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.29.
  15. J. Gajarský, S. Kreutzer, J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toruńczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic, 21(4):Article 29, 2020. URL: https://doi.org/10.1145/3382093.
  16. M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46superscriptth Annual ACM Symposium on Theory of Computing, STOC '14, pages 89-98, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591851.
  17. M. Grohe and D. Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM Journal on Computing, 44(1):114-159, 2015. URL: https://doi.org/10.1137/120892234.
  18. S. Guillemot and D. Marx. Finding small patterns in permutations in linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 82-101, 2014. URL: https://doi.org/10.1137/1.9781611973402.7.
  19. H.A. Kierstead and W.T. Trotter. Planar graph coloring with an uncooperative partner. J. Graph Theory, 18(6):569-584, 1994. URL: https://doi.org/10.1002/jgt.3190180605.
  20. L Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. Google Scholar
  21. J. Nešetřil and P. Ossona de Mendez. Linear time low tree-width partitions and algorithmic consequences. In STOC'06. Proceedings of the 38superscriptth Annual ACM Symposium on Theory of Computing, pages 391-400. ACM Press, 2006. URL: https://doi.org/10.1145/1132516.1132575.
  22. J. Nešetřil and P. Ossona de Mendez. Tree depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6):1022-1041, 2006. URL: https://doi.org/10.1016/j.ejc.2005.01.010.
  23. J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics, 29(3):760-776, 2008. URL: https://doi.org/10.1016/j.ejc.2006.07.013.
  24. J. Nešetřil and P. Ossona de Mendez. First order properties on nowhere dense structures. The Journal of Symbolic Logic, 75(3):868-887, 2010. URL: https://doi.org/10.2178/jsl/1278682204.
  25. J. Nešetřil and P. Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. URL: https://doi.org/10.1016/j.ejc.2011.01.006.
  26. J. Nešetřil and P. Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. 465 pages. Google Scholar
  27. J. Nešetřil and P. Ossona de Mendez. Existence of modeling limits for sequences of sparse structures. The Journal of Symbolic Logic, 84(2):452-472, 2019. URL: https://doi.org/10.1017/jsl.2018.32.
  28. J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Rankwidth meets stability. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2014-2033, 2021. URL: https://doi.org/10.1137/1.9781611976465.120.
  29. J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Linear rankwidth meets stability. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1180-1199, 2020. URL: https://doi.org/10.1137/1.9781611975994.72.
  30. J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Classes of graphs with low complexity: The case of classes with bounded linear rankwidth. European Journal of Combinatorics, 91:103223, 2021. Special issue dedicated to Xuding Zhu’s 60th birthday. URL: https://doi.org/10.1016/j.ejc.2020.103223.
  31. J. Nešetřil, P. Ossona de Mendez, and S. Siebertz. Towards an arboretum of monadically stable classes of graphs, 2020. URL: http://arxiv.org/abs/2010.02607.
  32. M. Pilipczuk, S. Siebertz, and S. Toruńczyk. On the number of types in sparse graphs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 799-808. ACM, 2018. URL: https://doi.org/10.1145/3209108.3209178.
  33. S. Plotkin, S. Rao, and W.D. Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 462-470. SIAM, 1994. URL: https://doi.org/10.5555/314464.314625.
  34. K.-P. Podewski and M. Ziegler. Stable graphs. Fund. Math., 100:101-107, 1978. Google Scholar
  35. F. Reidl, F.S. Villaamil, and K. Stavropoulos. Characterising bounded expansion by neighbourhood complexity. European Journal of Combinatorics, 75:152-168, 2019. URL: https://doi.org/10.1016/j.ejc.2018.08.001.
  36. N. Robertson and P.D. Seymour. Graph minors I-XXIII. J. Combin. Theory Ser. B, 1983-2010. Google Scholar
  37. S. Shelah. Classification theory and the number of non-isomorphic models. North-Holland, 1990. Google Scholar
  38. P. Simon and S. Toruńczyk. A model-theoretic characterization of bounded twin-width. personal communication, 2020. Google Scholar
  39. X. Zhu. Colouring graphs with bounded generalized colouring number. Discrete Math., 309(18):5562-5568, 2009. URL: https://doi.org/10.1016/j.disc.2008.03.024.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact