Florian Lehner's Webpage

About me

Florian Lehner

I am a post-doctoral researcher at the Institute of Discrete Mathematics at Graz University of Technology. My position is funded by the Austrian Science Fund (FWF) via projects Walks and boundaries — a wide range PI: W. Woess, project number P 31889-N35, and Graphs and groups Erwin Schrödinger Fellowship, project number J 3850-N32.

My research interests cover a wide variety of topics in graph theory and combinatorics. Much of my work concerns problems on the interface of group theory and graph theory, but I also enjoy working on topics with a geometric or probabilistic flavour.

Recent research

Asymmetric graph colouring

some distinguishing colourings How hard is it, to get rid of the symmetries of a discrete structure? More precisely, how many colours do we need to colour the vertices of a graph in a way that no automorphism except the identity preserves the colouring?

The least number of colours required is called the asymmetric colouring number or distinguishing number of the graph. I have studied this graph invariant in various settings, including random colourings, edge colourings, and most recently colourings of graphs with bounded maximum degree.

Combinatorial game theory

cops-and-robber game The study of pursuit-evasion games on graphs is a popular topic in combinatorial game theory. These are games where one player's objective is to capture the other player, whereas the other player attempts to avoid being captured. Notable examples include Cops-and-Robber and Conway's Angel-Devil game.

My contributions mostly concern the so-called cop number, that is, the least number of pursuers needed to guarantee capture in the Cops-and-Robber game, but I am always interested in learning about other aspects of the game as well as other combinatorial games.

Tree structure in infinite graphs

amalgamated free product structure Stallings' splitting theorem is one of the central results in geometric group theory. It essentially states that a finitely generated group satisfies one of two alternatives. It either has one well-connected infinite part (that is, it is one-ended), or it exhibits a large-scale tree structure (either an amalgamated free product, or a HNN extension).

Hamann, Miraftab, Rühmann, and I recently proved an analogous result for infinite graphs; I am currently working on applications as well as further extensions of this result.

Resume

You can also download a CV in PDF format.

Employment

Project Assistant Department of Discrete Mathematics, Graz University of Technology since 2020
Erwin Schrödinger Research Fellow Department of Mathematics, University of Warwick Department of Discrete Mathematics, Graz University of Technology since 2017
University Assistant Department of Mathematics, University of Hamburg 2015 – 2017
University Assistant Institute of Geometry, Graz University of Technology 2011 – 2015
Teaching Assistant Mathematics Institutes and Institute for Software Technology, Graz University of Technology 2007 – 2010

Education

PhD: Mathematics and Scientific Computing Graz University of Technology Graduation with highest distinctions "Sub auspiciis Praesidentis" Thesis: Symmetry breaking in graphs and groups. Adviser: J. Wallner 2011 – 2014
Master Programme: Mathematical Computer Science Graz University of Technology Thesis: The line graph of every locally finite 6-edge-connected graph with finitely many ends is hamiltonian. Adviser: W. Woess 2008 – 2011
Bachelor Programme: Technical Mathematics Graz University of Technology 2005 – 2008

Publications

You can also download a BibTeX-file of this list.

Articles

[35] Self-avoiding walks and multiple context-free languages. with C. Lindorfer 2020, preprint. pdf
[34] Hamiltonian decompositions of 4-regular Cayley graphs of infinite abelian groups. with J. Erde 2020, preprint. pdf
[33] On fixity of arc-transitive graphs. with P. Potočnik and P. Spiga 2020, preprint. pdf
[32] Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs". with G. Verret Ars Mathematica Contemporanea, 2020, to appear. doi pdf
[31] Comparing consecutive letter counts in multiple context-free languages. with C. Lindorfer 2020, preprint. pdf
[30] On asymmetric colourings of graphs with bounded degrees and infinite motion. with M. Pilśniak and M. Stawiski 2019, preprint. pdf
[29] A bound for the distinguishing index of regular graphs. with M. Pilśniak and M. Stawiski European Journal of Combinatorics, 89, 2020. doi pdf
[28] Bounding the cop number of a graph by its genus. with N. Bowler, J. Erde, and M. Pitz 2019, preprint. pdf
[27] On the cop number of toroidal graphs. 2019, preprint. pdf
[26] A Stallings' type theorem for quasi-transitive graphs. with M. Hamann, B. Miraftab, and T. Rühmann 2019, preprint. pdf
[25] Invariant spanning double rays in amenable groups. with A. Georgakopoulos 2018, preprint. pdf
[24] Distinguishing infinite graphs with bounded degrees. with M. Pilśniak and M. Stawiski 2018, preprint. pdf
[23] Distinguishing numbers of finite 4-valent vertex-transitive graphs. with G. Verret Ars Mathematica Contemporanea, 2020, to appear. doi pdf
[22] On symmetries of edge and vertex colourings of graphs. with S. M. Smith Discrete Mathematics, 343 (9), 2020. doi pdf
[21] Distinguishing density and the Distinct Spheres Condition. with W. Imrich and S. M. Smith European Journal of Combinatorics, 89, 2020. doi pdf
[20] Hamilton decompositions of one-ended Cayley graphs. with J. Erde and M. Pitz Journal of Combinatorial Theory, Series B, 140, pp. 171 – 191, 2020. doi pdf
[19] Trees with distinguishing index equal distinguishing number plus one. with S. Alikhani, S. Klavžar, and S. Soltani Discussiones Mathematicae Graph Theory, 40 (3), pp. 875 – 884, 2020. doi pdf
[18] Firefighting on trees and Cayley graphs. Australasian Journal of Combinatorics, 75 (1), pp. 66 – 72, 2019. jrnl pdf
[17] On tree-decompositions of one-ended graphs. with J. Carmesin and R. G. Möller Mathematische Nachrichten, 292 (3), pp. 524 – 539, 2018. doi pdf
[16] A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs. with N. Bowler, J. Erde, M. Merker, M. Pitz, and K. Stavropoulos Discrete Applied Mathematics, 229, pp. 151 – 153, 2017. doi pdf
[15] Non-reconstructible locally finite graphs. with N. Bowler, J. Erde, P. Heinig, and M. Pitz Journal of Combinatorial Theory, Series B, 133, pp. 122 – 152, 2018. doi pdf
[14] A counterexample to the reconstruction conjecture for locally finite trees. with N. Bowler, J. Erde, P. Heinig, and M. Pitz Bulletin of the London Mathematical Society, 49 (4), pp. 630 – 648, 2017. doi pdf
[13] Breaking graph symmetries by edge colourings. Journal of Combinatorial Theory, Series B, 127, pp. 205 – 214, 2017. doi pdf
[12] Fast factorization of Cartesian products of (directed) hypergraphs. with M. Hellmuth Theoretical Computer Science, 615, pp. 1 – 11, 2016. doi pdf
[11] Maximising the number of independent sets in connected graphs. with S. Wagner Graphs and Combinatorics, 33 (5), pp. 1103 – 1118, 2017. doi pdf
[10] Local finiteness, distinguishing numbers and Tucker's conjecture. with R. G. Möller Electronic Journal of Combinatorics, 22 (4), 2015, research paper #P4.19. doi pdf
[9] Pursuit evasion on infinite graphs. Theoretical Computer Science, 655 (Part A), pp. 30 – 40, 2016. doi pdf
[8] The Cartesian product of graphs with loops. with T. Boiko, J. Cuno, W. Imrich, and C. E. van de Woestijne Ars Mathematica Contemporanea, 11 (1), pp. 1 – 9, 2016. doi pdf
[7] Clique trees of infinite locally finite chordal graphs. with C. Temmel Electronic Journal of Combinatorics, 25 (2), 2018, research paper #P2.9. doi pdf
[6] Extending cycles locally to Hamilton cycles. with M. Hamann and J. Pott Electronic Journal of Combinatorics, 23 (1), 2016, research paper #P1.49. doi pdf
[5] Random colorings and automorphism breaking in locally finite graphs Combinatorics, Probability and Computing, 22 (6), pp. 885 – 909, 2013. doi pdf
[4] Distinguishing graphs with intermediate growth. Combinatorica, 36 (3), pp. 333 – 347, 2016. doi pdf
[3] Endomorphism breaking in graphs. with W. Imrich, R. Kalinowski, and M. Pilśniak Electronic Journal of Combinatorics, 21 (1), 2014, research paper #P1.16. doi pdf
[2] Distinguishing graphs with infinite motion and nonlinear growth. with J. Cuno and W. Imrich Ars Mathematica Contemporanea, 7, pp. 201 – 213, 2014. doi pdf
[1] On spanning tree packings of highly edge connected graphs. Journal of Combinatorial Theory, Series B, 105, pp. 93 – 126, 2014. doi pdf

Theses

[2] Symmetry breaking in graphs and groups Ph.D. Thesis, TU Graz, 2014. pdf
[1] The line graph of every locally finite 6-edge-connected graph with finitely many ends is hamiltonian. Master thesis, TU Graz, 2011. pdf