CCOSA project

CCOSA is a project funded by European Research Council (ERC) as a starting grant. Its principal investigator is Daniel Kráµ who is an associate professor at Charles University and who works on the project together with his young colleagues Zdeněk Dvořák, Vít Jelínek, Ondřej Pangrác, Robert ©ámal and their students. The project uses scientific and logistic background provided by Computer Science Institute and DIMATIA center at Charles University.

The full name of the project is "Classes of Combinatorial Objects - from Structure to Algorithms". The project started on December 1, 2010 and will last until November 30, 2015. In the framework of the project, we offer several types of visiting positions (see details below) and applications are welcomed during the whole period of the project. We also organize a small workshop in the fall 2011 on topics close to the project.

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.

Team members

Faculty: Zdeněk Dvořák, Daniel Kráµ (PI), Vít Jelínek (since June 2011), Ondřej Pangrác and Robert ©ámal

Students: Jan Hladký, Tereza Klimoąová, Lukáą Mach, Tomáą Toufar, Vojtěch Tůma and Jan Volec

Postdoc/student positions available!

At this moment, we do not accept any new applications for positions starting in 2011.

The project offers support for postdoctoral and visiting student positions during the course of the project. Starting dates and lengths of the positions are flexible. We prefer postdoctoral positions between 5 and 12 months with possible extension up to 24 months and visiting student scholarships between 2 and 4 monhts. Applicants interested in postdoctoral positions should obtain PhD before the position starts; those interested in student positions should be a full time PhD student at their own university.

In addition, with support of the ERC Starting grant CSP-Complexity of Manuel Bodirsky at LIX Ecole Polytechnique in Paris, one joint postdoc position is also offered. A successful candidate should have a strong background in logic or algorithmic graph theory and be willing to extend his/her expertise in the other field. A position is intended as a one-year position at Charles University in Prague and a one-year position at LIX Ecole Polytechnique in Paris. Informal inquiries for more details are welcomed by e-mail.

Postdocs and long-term visitors

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. FP7 logo

Modified: 12. 02. 2012