Skip to main content

ERC Starting grant CCOSA

CCOSA was a project funded by European Research Council (ERC) as a starting grant. Its principal investigator is Daniel Kráľ, and the full name of the project is "Classes of Combinatorial Objects - from Structure to Algorithms". The project started on December 1, 2010 and lasted until November 30, 2015. The host institution of the project was Charles University until September 30, 2012. Since October 1, 2012, the project was hosted by the University of Warwick.

In the fall 2011, we organized a small workshop on topics close to the project. We organized another research school related to the topics of the project in cooperation with University of West Bohemia in December 2013. In the early summer 2015, we organized the last research school supported by the project, which is also generously supported by LMS and CMI.

The publications obtained in the course of the project are listed on a separate web page.

Scientific goals of the project

The project aims at analyzing fundamental problems from combinatorics using the most current methods available and at providing new structural and algorithmic insights to such problems. The problems considered will be treated on a general level of classes of combinatorial objects of the same kind and the developed general methods will also be applied to specific open problems.

The project has two main areas. The first one is concerned with dense combinatorial objects. Such objects appear in extremal combinatorics and tools developed to handle them found their applications in different areas of mathematics and computer science. The project will focus on extending known methods to new classes of combinatorial objects, in particular those from algebra. We also intend to apply Razborov flag algebras to problems from extremal combinatorics. Applications of the obtained results in property testing will also be considered.

The other area of the project deals with techniques for sparse objects. Examples of sparse objects are graphs embeddable in a fixed surface and more general minor-closed classes of graphs. The project objectives include providing new structural results and algorithmic metatheorems for classes of sparse objects using both classical tools based on the theory of graph minors as well as new tools based on the framework of classes of nowhere-dense structures.

PhD students


  • Demetres Christofides, Dec 2010-Jul 2011, Charles University
  • Andrew Treglown, October 2011-September 2012, Charles University
  • Jan Mazák, October 2011-June 2012, Charles University
  • Roman Glebov, February 2013-August 2013, University of Warwick
  • Anita Liebenau, October 2013-August 2015, University of Warwick
  • Ping Hu, October 2014-November 2015, University of Warwick

Long-term visitors at Charles University

  • Luke Postle (Georgia Tech), April 2011-June 2011
  • Katherine Edwards (McGill), April 2011-June 2011
  • Archontia Giannopoulou (University of Athens), October 2011-March 2012
  • Roman Glebov (TU Berlin), April-August 2012

Long-term visitors at University of Warwick

  • Andrzej Grzesik (Jagiellonian University), January-March 2013, April-June 2014, and October-December 2014
  • Carl Yerger (Davidson), May-June 2013
  • Matjaz Krnc (University of Ljubljana), September-December 2013
  • Fiona Skerman (Oxford), October-November 2014
  • Francois Dross (ENS Lyon), January-March 2015

Collaborators at Charles University - until September 2012

Faculty: Zdeněk Dvořák, Vít Jelínek , Ondřej Pangrác and Robert Šámal

Students: Jan Hladký, Tomáš Toufar and Vojtěch Tůma

Funding info

ERC logo This project has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 259385. EU flag FP7 logo