Kolja Knauer Ramón y Cajal researcher Maître de conférences (on leave) Address: Universitat de Barcelona Departament de Matemàtiques i Informàtica Gran Via de les Corts Catalanes, 585 08007 Barcelona, Spain Email: firstname.lastname@domain domain =gmail.com Office: P232 ORCID: 0000-0002-8151-2184 Scopus: 29067881400

Research Interests
(ordered by length)

• Representations of oriented matroids and other oriented structures
• Geometric intersection graphs and geometric hypergraphs
• Lattices and polyhedra from graphs and matroids
• Graph drawing
• Cayley graphs
• Partial cubes

Grants

• Member of the ANR project DAGDigDec: ANR-21-CE48-0012: DAGs and Digraph Decompositions
• Member of the MICINN project ALCOIN: PID2019-104844GB-I00: Álgebra Conmutativa y sus interacciones
• Member of the ANR projet GATO: ANR-16-CE40-0009-01: Graphs, Algorithms and Topology
• Member of the ANR projet DISTANCIA: ANR-17-CE40-0015: Metric Graph Theory
• Member of the ANR projet CAPPS: ANR-17-CE40-0018: Combinatorial Analysis of Polytopes and Polyhedral Subdivisions
  past:
• Leader of the PEPS project Efficient Representations of Oriented Systems.
• Member of the ANR project Embedded Graphs and their Oriented Structures.
• Member of the ANR project New trends in matroids: base polytopes, algorithms, structures, and interactions.
• Member of the EuroGiga project Graph Drawings and Representations.

Events

• Organizing the Three Talks in Combinatorics seminar series at Universitat de Barcelona
  past:
• Organizing the conference Stefan is 60 in Berlin, September 2022.
• Lecturing BGSMath course Fragments of Algebraic Graph Theory with Miguel Angel Fiol Mora and Juilan Pfeifle
• Organizer of the weekly research seminar Réunion ACRO at LIS Marseille.
• Organizing the workshop Metrics in Marseille in Luminy, April 2018.
• Organizing the International workshop on graphs, semigroups, and semigroup acts in Berlin, October 2017.
• Organizing the EuroGIGA GraDR midterm meeting in Berlin, October 2012.
• Organizer of the weekly research seminar Mittagsseminar at TU Berlin.

Books

• Algebraic graph theory. Morphisms, monoids and matrices
  with Ulrich Knauer
  
• De Gruyter Studies in Mathematics, 331 pages, (2019)
  
  
• Diskrete und algebraische Strukturen - kurz gefasst
  with Ulrich Knauer
  
• Springer Spektrum, 271 pages, (2015)
  

Book chapters

• Popopo - posets, polynômes, polytopes
  
• Informatique Mathématique, une photographie en 2019, Jérémie Chalopin et Pierre Guillon (éd.), CNRS Editions (2019)
  

Preprints and Publications
(conferences and journals merged)

• The signed Varchenko Determinant for Complexes of Oriented Matroids
  with Winfried Hochstättler and Sophia Keip
  
  • (submitted)
  
  
• On endomorphism universality of sparse graph classes
  with Gil Puig i Surroca
  
  • (submitted)
  
  
• Lattice path matroids and quotients
  with Carolina Benedetti-Velásquez
  
  • (submitted)
  
  
• Beyond symmetry in generalized Petersen graphs
  with Ignacio García-Marco
  
  • (submitted)
  
  
• Kirchberger's Theorem for Complexes of Oriented Matroids
  with Winfried Hochstättler and Sophia Keip
  
  • (submitted)
  
  
• Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
  with Hoang La and Petru Valicov
  
  • Electronic Journal of Combinatorics (accepted)
  
  
• Ehrhart theory of lattice path matroid polytopes
  with Carolina Benedetti-Velásquez and Jerónimo Valencia
  
  • (submitted)
  
  
• Labeled sample compression schemes for complexes of oriented matroids
  with Victor Chepoi and Manon Philibert
  
  • (submitted)
  
  
• On monoid graphs
  with Gil Puig i Surroca
  
  • Mediterranean Journal of Mathematics (accepted)
  
  
• On the dichromatic number of surfaces
  with Pierre Aboulker, Frédéric Havet, and Clément Rambaud
  
  • Electronic Journal of Combinatorics, 29 (1), p1.30, (2022)
  • Extended Abstracts EuroComb 2021, Trends in Mathematics, 14, (2021)
  
  
• Finitary affine oriented matroids
  with Emanuele Delucchi
  
  • FPSAC 2021 (accepted as poster)
  
  
• Colouring bottomless rectangles and arborescences
  with Jean Cardinal, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, and Narmada Varadarajan
  
  • (submitted)
  
  
• On sensitivity in bipartite Cayley graphs
  with Ignacio García-Marco
  
  • Journal of Combinatorial Theory, Series B, 154, pages 211-238 (2022)
  
  
• Ample completions of oriented matroids and complexes of uniform oriented matroids
  with Victor Chepoi and Manon Philibert
  
  • SIAM Journal of Discrete Mathematics, 36(1), pages 509-535, (2022)
  
  
• Plattenbauten: Touching Rectangles in Space
  with Stefan Felsner and Torsten Ueckerdt
  
  • Graph-Theoretic Concepts in Computer Science, WG2020, 13, (2020)
  
  
• Corners and simpliciality in oriented matroids and partial cubes
  with Tilen Marc
  
  • (submitted)
  
  
• Cayley posets
  with Ignacio García-Marco and Guillaume Mercui-Voyant
  
  • Mediterranean Journal of Mathematics, 17(186), (2020)
  
  
• Planar cubic graphs of small diameter
  with Piotr Micek
  
  • only on arXiv
  
  
• Enumerating k-arc-connected orientations
  with Sarah Blind and Petru Valicov
  
  • Algorithmica, 82, pages 3588-3603 (2020)
  
  
• On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs
  with Sandi Klavžar and Tilen Marc
  
  • MATCH Commun. Math. Comput. Chem., 86, pages 327-342, (2021)
  
  
• Two-dimensional partial cubes
  with Victor Chepoi and Manon Philibert
  
  • Electronic Journal of Combinatorics, 27 (40), p3.29, (2020)
  
  
• Complete Acyclic Colorings
  with Stefan Felsner, Winfried Hochstättler, and Raphael Steiner
  
  • Electronic Journal of Combinatorics, 27 (2), p2.40, (2020)
  
  
• Flip distances between graph orientations
  with Oswin Aichholzer, Jean Cardinal, Tony Huynh, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber
  
  • Algorithmica, 83, pages 116-143 (2021)
  • Graph-Theoretic Concepts in Computer Science, WG2019, pages 120-134, (2019)
  
  
• Abelian doppelsemigroups
  with Anatolii V. Zhuchok
  
  • Algebra and Discrete Mathematics, 26 (2), pages 290-304, (2019)
  
  
• The queue-number of posets of bounded width or height
  with Piotr Micek and Torsten Ueckerdt
  
  • Lecture Notes in Computer Science 11282, GD 2018, pages 200-212 (2018)
  
  
• The interval number of a planar graph is at most three
  with Guillaume Guégan, Jonathan Rollin and Torsten Ueckerdt
  
  • Journal of Combinatorial Theory, Series B, 146, pages 61-67, (2021)
  
  
• Chomp on generalized Kneser graphs and others
  with Ignacio García-Marco and Luis Pedro Montejano
  
  • International Journal of Game Theory, 50, pages 603-621 (2021)
  
  
• Cuts in matchings of 3-connected cubic graphs
  with Petru Valicov
  
  • European Journal of Combinatorics, 76, pages 27-36, (2019)
  
  
• Computing metric hulls in graphs
  with Nicolas Nisse
  
  • Discrete Mathematics & Theoretical Computer Science, 21 (1), ICGT 2018, (2019)
  
  
• Decomposing 4-connected planar triangulations into two trees and one path
  with Torsten Ueckerdt
  
  • Journal of Combinatorial Theory Series B, 134, pages 88-109, (2019)
  
  
• Chomp on numerical semigroups
  with Ignacio García-Marco
  
  • Algebraic Combinatorics, 1 (3), pages 371-394, (2018)
  
  
• On tope graphs of complexes of oriented matroids
  with Tilen Marc
  
  • Discrete & Computational Geometry, 63 (2), pages 377-417, (2020)
  
  
• On lattice path matroid polytopes: integer points and Ehrhart polynomial
  with Leonardo Martínez-Sandoval and Jorge Luis Ramírez Alfonsín
  
  • Discrete & Computational Geometry, 60 (3), pages 698-719 (2018)
  
  
• A correction of a characterization of planar partial cubes
  with Rémi Desgranges
  
  • Discrete Mathematics, 340 (6), pages 1151-1153 (2017)
  
  
• Hypercellular graphs: partial cubes without Q₃^- as partial cube minor
  with Victor Chepoi and Tilen Marc
  
  • Discrete Mathematics, 343 (4), (2020)
  
  
• A Tutte polynomial inequality for lattice path matroids
  with Leonardo Martínez-Sandoval and Jorge Luis Ramírez Alfonsín
  
  • Advances in Applied Mathematics, 94, pages 23-38 (2018)
  
  
• COMs: Complexes of Oriented Matroids
  with Hans-Jürgen Bandelt and Victor Chepoi
  
  • Journal of Combinatorial Theory Series A, 156, pages 195-237 (2018)
  
  
• Graph Drawings with One Bend and Few Slopes
  with Bartosz Walczak
  
  • Lecture Notes in Computer Science, 9644, pages 549-561, LATIN, (2016)
  
  
• Drawing graphs with vertices and edges in convex position
  with Ignacio García-Marco
  
  • Computational Geometry: Theory and Applications58, pages 25-33, (2016)
  • Lecture Notes in Computer Science, 9411, pages 348-359, GD, (2015)
  
  
• Planar digraphs without large acyclic sets
  with Petru Valicov and Paul S. Wenger
  
  • Journal of Graph Theory, 85 (1), pages 288-291, (2017)
  
  
• On the structure of Schnyder woods on orientable surfaces
  with Daniel Gonçalves and Benjamin Lévêque
  
  • Journal of Computational Geometry, 10 (1), pages 127-163, (2019)
  
  
• Orienting Triangulations
  with Boris Albar and Daniel Gonçalves
  
  • Journal of Graph Theory, 83 (4), pages 392-405, (2016)
  • Proceedings EuroCG, (2015)
  
  
• How many circuits determine an oriented matroid?
  with Luis Pedro Montejano and Jorge Luis Ramírez Alfonsín
  
  • Combinatorica, 38 (4), pages 861-885, (2018)
  
  
• Intersection Graphs of L-Shapes and Segments in the Plane
  with Stefan Felsner, George B. Mertzios, and Torsten Ueckerdt
  
  • Discrete Applied Mathematics, 206, pages 48-55, (2016)
  • Lecture Notes in Computer Science, 8635, pages 299-310, MFCS, (2014)
  
  
• Online and Size Anti-Ramsey Numbers
  with Maria Axenovich, Judith Stumpp, and Torsten Ueckerdt
  
  • Journal of Combinatorics, 5(1), pages 87-114, (2014)
  
  
• Convexity in Partial Cubes: the Hull Number
  with Marie Albenque
  
  • Discrete Mathematics, 339, pages 866-876, (2016)
  • Lecture Notes in Computer Science, 8392, pages 421-432, LATIN, (2014)
  
  
• On planar right groups
  with Ulrich Knauer
  
  • Semigroup Forum, 92 (1), pages 142-157, (2016)
  
  
• Making Octants Colorful, and Related Covering Decomposition Problems
  with Jean Cardinal, Piotr Micek, and Torsten Ueckerdt
  
  • SIAM Journal of Discrete Mathematics, 28(4), pages 1948-1959, (2014)
  • Proceedings of SODA 2014, pages 1424-1432, (2014)
  
  
• Connected Covering Numbers
  with Jonathan Chappelon, Luis Pedro Montejano, and Jorge Luis Ramírez Alfonsín
  
  • Journal of Combinatorial Designs, 23 (12), pages 534-549, (2015)
  
  
• Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
  with Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sebastien Collette, Thomas Hackl, Michael Hoffmann, Stefan Langerman, Michał Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt
  
  • Lecture Notes in Computer Science, 8037, pages 73-84, WADS, (2013)
  
  
• Making Triangles Colorful
  with Jean Cardinal, Piotr Micek, and Torsten Ueckerdt
  
  • Journal of Computational Geometry 4 (1), pages 240-246, (2013)
  
  
• Classification of coupled dynamical systems with multiple delays: Finding the minimal number of delays
  with Leonhard Lücken and Jan Philipp Pade
  
  • SIAM Journal of Applied Dynamical Systems, 14 (1), pages 286-304, (2015)
  • with Serhiy Yanchuk in Europhysics Letters103, 6 pages, (2013)
  
  
• Simple treewidth
  with Torsten Ueckerdt
  
  • Midsummer Combinatorial Workshop Prague (2012)
  
  
• A Graph-Theoretical Axiomatization of Oriented Matroids
  with Juan José Montellano-Ballesteros and Ricardo Strausz
  
  • European Journal of Combinatorics, 35 (1), pages 388-391, (2014)
    
  • Electronic Notes in Discrete Mathematics, 38, pages 523-528, EuroComb, (2011)
  
  
• Outerplanar graph drawings with few slopes
  with Piotr Micek and Bartosz Walczak
  
  • Computational Geometry: Theory and Applications, 47 (5), pages 614-624, (2014)
  • Lecture Notes in Computer Science, 7434, pages 323-334, COCOON, (2012)
  • Proceedings EuroCG, (2012)
  
  
• Three ways to cover a graph
  with Torsten Ueckerdt
  
  • Discrete Mathematics, 339, pages 745-758, (2016)
  
  
• On the Duality of Semiantichains and Unichain Coverings
  with Bartłomiej Bosek, Stefan Felsner, and Grzegorz Matecki
  
  • Order, 33 (1), pages 29-38, (2016)
  • Lecture Notes in Computer Science, 7353, pages 43-51, CSR, (2012)
  
  
• On the bend-number of planar and outerplanar graphs
  with Daniel Heldt and Torsten Ueckerdt
  
  • Discrete Applied Mathematics 179, pages 109-119, (2014)
  • Lecture Notes in Computer Science7256, pages 458-469, LATIN, (2012)
  
  
• Edge-intersection graphs of grid paths: the bend-number
  with Daniel Heldt and Torsten Ueckerdt
  
  • Discrete Applied Mathematics, 167, pages 144-162 , (2014)
  
  
• Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids
  with Stefan Felsner, Ricardo Gómez, Juan José Montellano-Ballesteros and Ricardo Strausz
  
  • European Journal of Combinatorics, 32 (1), pages 60-66, (2011)
  
  
• Polynomial Time Recognition of Uniform Cocircuit Graphs
  with Ricardo Gómez, Juan José Montellano-Ballesteros and Ricardo Strausz
  
  • Electronic Notes in Discrete Mathematics, 35, pages 29-34, LAGOS, (2009)
  
  
• Toroidal Embeddings of Right Groups
  with Ulrich Knauer
  
  • Thai Journal of Mathematics, 8 (3), pages 483-490, (2010)
  
  
• Chip-Firing, Antimatroids, and Polyhedra
  
  • Electronic Notes in Discrete Mathematics, 34, pages 9-13, EuroComb, (2009)
  
  
• How to Eat 4/9 of a Pizza
  with Piotr Micek and Torsten Ueckerdt
  
  • Discrete Mathematics, 311 (16), pages 1635-1645, (2011)
  
  
• Distributive Lattices, Polyhedra, and Generalized Flow
  with Stefan Felsner
  
  • European Journal of Combinatorics, 32 (1), pages 45-59, (2011)
  
  
• ULD-Lattices and Δ-Bonds
  with Stefan Felsner
  
  • Combinatorics, Probability and Computing, 18 (5), pages 707-724, (2009)
  
  
• Distributive Lattices from Graphs
  with Stefan Felsner
  
  • Proceedings of VI. Jornadas de Matematica Discreta y Algoritmica Lleida, pages 11-23, (2008)
  
  
• Distributive Lattices on Graph Orientations
  
  • Proceedings of the International Conference on Semigroups, Acts and Categories
    with Applications to Graphs, pages 79-91, (2007)
  
  

Theses

• Oriented matroids and beyond: complexes, partial cubes, and corners
  Habilitation Thesis, 215 pages, (2021)
  
• Lattices and Polyhedra from Graphs
  PhD Thesis, 131 pages, (2010)
  
• Partial Orders on Orientations via Cycle Flips
  Diploma Thesis, 85 pages, (2007)

PhD students

• Manon Philibert: Cubes partiels : complétion, compression, plongement ( 2018-2021 )
  
• Sarah Blind: Output-sensitive algorithms for enumeration problems in graphs ( 2016--2019 )
  
• Tilen Marc: Cycling in hypercubes ( 2015-2018)

Graphs

• all minimal Cayley graphs of groups on up to 107 elements, (I also have them up to 127)
  in the file the g6 encoding of each such graph is preceeded by a line of the form n k [some permutations], which gives a representation as Cayley graph of SmallGroup(n,k) as in GAP with respect to generators represented by the permutations
  

Last update January 2023