Combinatorics and graph theory

Combinatorics and graph theory

The group collaborates with the theoretial computer science group and several groups abroad. Modern discrete mathematics consists of several interrelated disciplines. The research and teaching is performed on two main fronts.

Combinatorics and graph theory

Discrete situations, relations and structures, usually involving only finitely many objects, are modelled. A typical problem is of assigning numbers (codes of transmission channels) to nodes (transmitters) so that two adjacent nodes (close transmitters) get numbers with difference at least 2 (to avoid interference). Close relation to practical applications is obvious. Other research topics include investigation of data structures (numbers of calls to the memory, expected complexity etc.). The group has excellent results in structural graph theory, graph and hypergraph colorings, in Ramsey theory and in intersection of combinatorics and computational complexity. The projects being solved by the group are “Complex Structures – Regularities in Combinatorics and Discrete Mathematics (Cores)” and “Center of Excellence – Institute for Theoretical Computer Science”, which also involves the other three groups, namely the geometry group, the computational complexity group, and the algorithms and optimization group.

Discrete and computational geometry

Geometry is perhaps the oldest branch of mathematics, but Discrete and computational geometry is much younger. It is busy with questions on possible configurations of points, lines, curves and so on, and with the computational aspects. For illustration we mention an important problem of the trisector curve, solved by the late J. Matoušek and his collaborators from Japan.

The group has excellent results on both geometric and topological graphs, in graph drawing, in computational geometry, in topological methods in combinatorics, in geometric Ramsey theory.

Selected outputs:

  • Jaroslav Nešetřil, Patrice Ossona de Mendez, Sparsity, Springer, Heidelberg 2012. xxiv+457 pp.

  • Zdeněk Dvořák, Daniel Kráľ, Robin Thomas, Testing first-order properties for subclasses of sparse graphs, J. ACM 60 (2013), no. 5, Art. 36, 24 pp.

  • Matt DeVos, Bojan Mohar, Robert Šámal, Unexpected behaviour of crossing sequences, J. Combin. Theory Ser. B 101 (2011), no. 6, 448–463.

  • Jiří Matoušek, Martin Tancer, Uli Wagner, Hardness of embedding simplicial complexes in Rd, J. Eur. Math. Soc. (JEMS), 12 (2011), no. 2, 259–295.

  • Jan Kynčl, Improved enumeration of simple topological graphs, Discrete Comput. Geom. 50 (2013), 727–770.

  • Jens M. Schmidt, Pavel Valtr, Cubic plane graphs on a given point set, Comput. Geom. 48 (2015), no. 1, 1–13.

Last change: December 15, 2015 10:57 
Share on:  
Contact Us

Charles University

Ovocný trh 5

Prague 1

116 36

Czech Republic

Centre for Information, Counselling and Social Services


Phone: +420 224 491 850

Public Relations Officer


Phone: +420 224 491 248

Data Box ID: piyj9b4

ID No.: 00216208

VAT No.: CZ00216208

How to Reach Us