Scope
STRUCO is an Associated International Laboratory of CNRS between IÚUK,
Prague, and IRIF (formerly LIAFA), Paris.
The primary theme of the laboratory is graph theory, more specifically:
- sparsity of graphs (nowhere dense classes of graphs, bounded expansion classes of graphs);
- extremal graph theory;
- graph coloring;
- Ramsey theory, universality and morphism duality;
- graph and matroid algorithms and model checking.
STRUCO focuses on high-level study of fundamental combinatorial objects,
with a particular emphasis on comprehending and disseminating the state-of-the-art theories and techniques
developed. The obtained insights shall be applied to obtain new results on existing problems as well as to identify directions and questions for future work.
One of the main goals of STRUCO is to provide a sustainable and reliable structure to help Czech and French researchers cooperate on long-term projects, disseminate
the results to students of both countries and create links between these students more systematically.
The chosen themes of the project indeed cover timely and difficult questions,
for which a stable and significant cooperation structure is needed. By
gathering an important number of excellent researchers and students, the
LEA will create the required environment for making advances, which
shall be achieved not only by short-term exchanges of researchers, but
also by a strong involvement of Ph. D students in the learning of
state-of-the-art techniques and in the international collaborations.
STRUCO is a natural place to federate and organize these many isolated collaborations between our two countries.
Thus, the project would ensure long-term cooperations and allow young researchers (especially PhD students) to maintain the fruitful exchanges between the two countries in the future years,
in a structured and federated way.
Activities
Events
The following events benefited the support of the STRUCO Laboratory.
- Meetings on Graph Theory and Sparse Structures, 15--17 May 2019, IRIF, Paris
- 40 Years of Graphs and Algorithms, 11--12 October 2018, IRIF Paris
- Meetings on Graph Theory and Sparse Structures, 05--08 November 2017, Strasbourg
- Meetings on Graph Theory and Sparse Structures, 08--09 June 2015, Paris IHP
- Meetings on Graph Theory and Sparse Structures, 27--28 October 2014, Prague
- Meeting on Combinatorics & Distributed Computing, 12--15 November 2013, Pont-à-Mousson.
- Kick-off Meeting, 6--8 December 2011, Paris.
Internships & Visits
The following internships and visits fall within the scope of STRUCO; they were funded thanks to various sources (ANR, CE-ITI, DIMATIA, ERC, PHC, STRUCO).
- Rémi de Joannis de Verclos, (ENS Lyon), 2-month internship (from June 9th to August 4th, 2012) at the University of West Bohemia (Plzen) and Charles University (Prague) under the joint supervision of T. Kaiser and M. Loebl.
- Ján Mazák, (Charles University), visited LIAFA from March 12th to 16th, 2012.
- Daniel Král', (Charles University), visited LIAFA
from March 12th to 16th, 2012.
- Jaroslav Nešetřil, (Charles University), visited EHESS
from April 11th to May 4th, 2012.
- Daniel Král', (Charles University), visited LORIA
from September 23rd to 28th, 2012.
- Jan Volec, (Charles University and Univ. Paris Diderot), visited LORIA
from September 23rd to December 21st, 2012.
- Zdeněk Dvořák, (Charles University), visited LORIA
from November 18th to 23rd, 2012.
- Jaroslav Nešetřil, (Charles University), visited EHESS
from December 7th to 10th, 2012.
- Jaroslav Nešetřil, (Charles University), visited EHESS
from April 22nd to May 25th, 2013.
- Martin Loebl, (Charles University), visited LORIA
from June 23rd to 27th, 2013.
- Zdeněk Dvořák, (Charles University), visited LORIA
from July 22nd to 27th, 2013.
- Jan Volec, (Warwick University and Univ. Paris Diderot), visited LORIA
from July 22nd to 27th, 2013.
- Jan Volec, (Warwick University and Univ. Paris Diderot), visited LORIA
from January 13th to May 12th, 2014.
- Zdeněk Dvořák, (Charles University), visited LORIA
from January 27th to February 2nd, 2014.
- Jaroslav Nešetřil, (Charles University), visited EHESS
from April 26th to May 30th, 2014.
- Martin Loebl, (Charles University), visited LORIA
from June 22rd to 25th, 2014.
- Zelealem Yilma, (LIAFA), visited the University of West Bohemia
from January 30th to February 4th, 2012.
- Jean-Sébastien Sereni, (LIAFA), visited Charles University
from March 19th to 26th, 2012.
- Patrice Ossona de Mendez, (EHESS), visited Charles University
from August 8th to 13th, 2012.
- Patrice Ossona de Mendez, (EHESS), visited Charles University
from September 15th to October 14th, 2012.
- Rémi de Joannis de Verclos, (ENS Lyon), visited Charles
University from October 28th to November 3rd
2012.
- Antoine Mamcarz, (LIAFA), visited Charles University from July,
27th to August 3rd, 2012.
- Patrice Ossona de Mendez, (EHESS), visited Charles University from
November 28th to December 21st, 2012.
- Jean-Sébastien Sereni, (LIAFA), visited Charles University
from December 3rd to 7th, 2012.
- Michel Habib, (LIAFA), visited Charles University
from December 10th to 14th, 2012.
- Florent Jouve (Univ. Orsay), visited Charles University
from January 28th to February 1st, 2013.
- Jean-Sébastien Sereni, (LORIA), visited Charles University
from January 28th to February 1st, 2013.
- Patrice Ossona de Mendez, (EHESS), visited Charles University from
March 17th to April 12th, 2013 and participated
to the study group "Limits of Structures" in Oberwolfach.
- Lucas Hosseini, (Univ. Paris Diderot), visited Charles University from
March 25th to April 5th, 2013 and participated
to the study group "Limits of Structures" in Oberwolfach.
- Jean-Sébastien Sereni, (LORIA), visited Charles University
from April 6th to 11th, 2013.
- Patrice Ossona de Mendez, (EHESS), visited Charles University from
June 3rdth to 16th, 2013.
- Jean-Sébastien Sereni, (LORIA), visited Charles University
from November 16th to 23rd, 2013.
- Lucas Hosseini, (Univ. Paris Diderot), visited Charles University from
February 3rd to 14th, 2014.
- Lucas Hosseini, (Univ. Paris Diderot), Rémi de Joannis de Verclos,
(ENS Lyon) and George Manoussakis (Univ. Paris Diderot) participated at the
Spring School in Combinatorics organized by Charles University at Lomnice nad
Popelkou from May 4th to 11th 2014.
- Patrice Ossona de Mendez, (EHESS), visited Charles University from
July 20th to August, 1st, 2014.
- Jean-Sébastien Sereni, (LORIA), visited Charles University
from July 21st to 26th, 2014.
Publications
The following publications fall in the scope of the STRUCO Laboratory.
Publications in International Journals
Colouring edges with many colours in cycles
J. Nešetřil,
P. Ossona de Mendez and
X. Zhu
Journal of Combinatorial Theory Series B, forthcoming.
On First-Order Definable Colorings
J. Nešetřil and
P. Ossona de Mendez
Geometry, Structure and Randomness in Combinatorics, forthcoming.
Subcubic triangle-free graphs have fractional chromatic number at most 14/5
Z. Dvořák,
J.-S. Sereni and
J. Volec
Journal of the London Mathematical Society, 89(3):641--662, 2014.
A new bound for the 2/3 conjecture
D. Král',
C.-H. Liu,
J.-S. Sereni,
P. Whalen and
Z. Yilma
Combinatorics, Probability and Computing, 22(3):384--393, 2013.
A note on Fiedler value of classes with sublinear separators
J. Nešetřil and
P. Ossona de Mendez
Linear Algebra and its Applications, 439:2216--2221, 2013.
Multiple Petersen subdivisions in permutation graphs
T. Kaiser,
J.-S. Sereni
and
Z. Yilma
The Electronic Journal of Combinatorics, 20:#P11, 9pp., 2013.
A model theory approach to structural limits
J. Nešetřil and
P. Ossona de Mendez
Commentationes Mathematicæ Universitatis Carolinæ, 53(4):581–603, 2012.
A new lower bound based on Gromov’s method of selecting heavily covered points
D. Král',
L. Mach and
J.-S. Sereni
Discrete and Computational Geometry, 48(2):487--498, 2012.
Characterizations and examples of graph classes with bounded expansion
J. Nešetřil,
P. Ossona de Mendez and
D. R. Wood
European Journal of Combinatorics, 33(3):350–373, 2012.
Min-max relations for odd cycles in planar graphs
D. Král',
J.-S. Sereni and
L. Stacho
SIAM Journal on Discrete Mathematics, 26(3):884--895, 2012.
Publications in International Conferences
Subcubic triangle-free graphs have fractional chromatic number at most 14/5
Z. Dvořák,
J.-S. Sereni and
J. Volec
In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2013), CRM Series 16:497--502, 2013.
Manuscripts and Papers Submitted for Publication
A note on acyclic vertex-colorings
J.-S. Sereni and
J. Volec
arXiv:1312.5600.
A distributed low Tree-depth decomposition algorithm for Bounded Expansion classes
J. Nešetřil and
P. Ossona de Mendez
A unified approach to structural limits, and limits of graphs with
bounded tree-depth
J. Nešetřil and
P. Ossona de Mendez
arXiv:1303.6471.
Fractional coloring of triangle-free planar graphs
Z. Dvořák,
J.-S. Sereni and
J. Volec
arXiv:1402.5331.
Modeling Limits in Hereditary Classes: Reduction and Application to Trees
J. Nešetřil and
P. Ossona de Mendez
arXiv:1312.0441.
A note on circular chromatic number of graphs with large girth and similar problems
J. Nešetřil and
P. Ossona de Mendez
arXiv:1402.3142.
Potts partition function and isomorphisms of trees
M. Loebl and
J.-S. Sereni
arXiv:1405.4132
Strongly polynomial sequences as interpretations
A. Goodall,
J. Nešetřil and
P. Ossona de Mendez
arXiv:1405.2449.
