^{th}Polish Combinatorial Conference

Będlewo, September 17-21, 2012

The scientific program consists of invited 60 minute lectures, contributed 20 minute talks, and two, whole day long, tutorials for PhD students. The conference will start with the Sunday dinner and end with the Friday breakfast. The lectures are planned for Monday – Thursday, while the day of tutorials is friday.

Book of abstracts: [pdf]

Slides of Kowalik’s tutorial: [pdf]

Program outline:

Monday | Tuesday | Wednseday | Thursday | Friday | |||||

breakfast | |||||||||

opening | Tibor Szabó tutorial Positional Games: The Neighborhood Conjecture and its neighborhood |
||||||||

Endre Szemerédi | Noga Alon | Mathias Schacht | Wojciech Szpankowski | ||||||

coffee | |||||||||

Anders Björner | Dieter Kratsch | Jesse-Józefczyk | Stojakovic | Glebov | Sułkowska | Łukasz Kowalik tutorial Algebraic approach to exact algorithms |
|||

Young | Bednarska-Bzdęga | Perarnau | Grosu | ||||||

Kotlar | Węsek | Narins | West | Plachta | Clemens | Ostroumova | Krawczyk | ||

Lasoń | Nikodem | Żak | Skowronek-Kaziów | Ponomarenko | Mikalački | Przykucki | Krysztowiak | ||

Lubawski | Fiedorowicz | Mieczkowska | Pilśniak | Goldshteyn | Ben-Ameur | Uzzell | Gropp | ||

lunch | |||||||||

Khachatrian | Kisielewicz | Shabanov | Raigorodskii | excursion | Czumaj | Lapinskas | Tibor Szabó (lecture continued, exercises) |
||

Anholcer | Grech | Kozik | Samirov | Savić | Staden | ||||

Gągol | Milans | Balachandran | Cherkashin | Rzążewski | Lo | ||||

Biro | Zhukovskii | Tuza | Kokotkin | Junosza-Szaniawski | Knox | ||||

Tsuchiiya | Droz | ||||||||

coffee | coffee | ||||||||

open mind award ceremony |
Bielak | Bloznelis | Baudon | Patkos | Łukasz Kowalik (lecture continued, exercises) |
||||

Kupavskii | Rybarczyk | Bensmail | Kieliszek | ||||||

Jakub Przybyło | Dzido | Kurauskas | Fulek | Šarka | |||||

Wojciech Samotij | Gordinowicz | Pawlik | Walczak | Ulas | |||||

Krzywdziński | Micek | Jochemko | Amani | ||||||

dinner | banquet | dinner | |||||||

open problems session | Tibor Szabó (solutions) |
||||||||

Łukasz Kowalik (solutions) |

Program:

Sunday, September 16:

*arrival day*- 19:00 - 21:00
*dinner*

- 19:00 - 21:00
Monday, September 17

8:00 - 9:00

*breakfast*9:00

*opening remarks*9:10 - 10:10 Endre Szemerédi,

*On the absorption method*10:10 - 10:30

*coffee*10:30 - 11:30 Anders Björner,

*Graph properties from a topological perspective — what, how and why*- 11:45 - 13:00
*contributed talks*(two parallel sessions 3+3) session 1A

- 11:45 - 12:10 Daniel Kotlar,
*On Extensions of the Alon-Tarsi Latin Square Conjecture* - 12:10 - 12:35 Michał Lasoń,
*Splitting multidimensional necklace problem* - 12:35 - 13:00 Wojciech Lubawski,
*Online list coloring of matroids*

session 1B

- 11:45 - 12:10 Krzysztof Węsek,
*b-bounded circular coloring of graphs* - 12:10 - 12:35 Mateusz Nikodem,
*Property stability of graphs* - 12:35 - 13:00 Anna Fiedorowicz,
*Acyclic improper colourings of graphs with fixed maximum degree*

- 11:45 - 12:10 Daniel Kotlar,

- 11:45 - 13:00
13:00

*lunch*- 14:15 - 16:30
*contributed talks*(two parallel sessions 5+5; 10min break after 3rd talk) session 2A

- 14:15 - 14:40 Hrant Khachatrian,
*Interval total colorings of complete multipartite graphs* - 14:40 - 15:05 Marcin Anholcer,
*Group irregularity strength of digraphs* - 15:05 - 15:30 Adam Gągol,
*Structure of Weighted Graphs with Forbidden Subdivision and Graph Sharing Games* - 15:40 - 16:05 Csaba Biro,
*The rate of growth of the minimum clique size of graphs of given order and chromatic number* - 16:05 - 16:30 Shoichi Tsuchiiya,
*Forbidden pairs for the existence of a homeomorphically irreducible spannig tree*

session 2B

- 14:15 - 14:40 Andrzej Kisielewicz,
*A progress in the Cerny conjecture* - 14:40 - 15:05 Mariusz Grech,
*Černý* - 15:05 - 15:30 Kevin Milans,
*Forbidden induced posets in the boolean lattice* - 15:40 - 16:05 Maksim Zhukovskii,
*On the convergence of probabilities of first-order properties when the zero-one k-law for random graphs doesn’t hold* - 16:05 - 16:30 Jean-Marie Droz,
*Homotopy theories for a category of graphs*

- 14:15 - 14:40 Hrant Khachatrian,

- 14:15 - 16:30
16:30

*coffee*17:00

*Open Mind Award ceremony*- 17:10 - 18:55
*nominees’ talks alphabetically*(35 minutes each) - 17:10 - 17:45 Jakub Przybyło,
*Challenges and landmarks in vertex distinguishing graph colourings* - 17:45 - 18:20 Wojciech Samotij,
*Independent sets in hypergraphs*

- 17:10 - 17:45 Jakub Przybyło,

- 17:10 - 18:55
19:00

*dinner*

Tuesday, September 18

8:00 - 9:00

*breakfast*9:00 - 10:00 Noga Alon,

*Coloring random Cayley graphs*10:00 - 10:30

*coffee*10:30 - 11:30 Dieter Kratsch,

*Exact exponential algorithms*- 11:45 - 13:00
*contributed talks*(two parallel sessions 3+3) session 3A

- 11:45 - 12:10 Lothar Narins,
*Ryser’s Conjecture and Home-Base Hypergraphs* - 12:10 - 12:35 Andrzej Żak,
*Hamilton saturated hypergraphs of essentially minimum size* - 12:35 - 13:00 Katarzyna Mieczkowska,
*On matchings in hypergraphs*

session 3B

- 11:45 - 12:10 Douglas West,
*1,2,3-Conjecture and 1,2-Conjecture for graphs with maximum average degree less than 8/3* - 12:10 - 12:35 Joanna Skowronek-Kaziów,
*Multiplicative Vertex-Colouring Weightings of Graphs* - 12:35 - 13:00 Monika Pilśniak,
*Endomorphism Breaking in Graphs*

- 11:45 - 12:10 Lothar Narins,

- 11:45 - 13:00
13:00

*lunch*- 14:15 - 15:55
*contributed talks*(two paralell sessions 4+4) session 4A

- 14:15 - 14:40 Dmitry Shabanov,
*Colorings of uniform hypergraphs with large girth* - 14:40 - 15:05 Jakub Kozik,
*Entropy compression for graph colouring problems* - 15:05 - 15:30 Niranjan Balachandran,
*Combinatorial Batch codes and an extremal Hypergraph Problem* - 15:30 - 15:55 Zsolt Tuza,
*Turan numbers and batch codes*

session 4B

- 14:15 - 14:40 Andrei Raigorodskii,
*On the chromatic numbers of spaces with sets of forbidden equilateral triangles* - 14:40 - 15:05 Dmitri Samirov,
*Coloring spaces without forbidden configurations* - 15:05 - 15:30 Danila Cherkashin,
*On the chromatic numbers of small-dimensional spaces* - 15:30 - 15:55 Andrei Kokotkin,
*On the realization of random graphs by graphs of diameters*

- 14:15 - 14:40 Dmitry Shabanov,

- 14:15 - 15:55
15:55 - 16:30

*coffee*- 16:30 - 18:55
*contributed talks*(two paralell sessions 5+5; 10min break after 3rd talk) session 5A

- 16:30 - 16:55 Halina Bielak,
*Multicolor Ramsey numbers for some forests and cycles* - 16:55 - 17:20 Andrey Kupavskii,
*On some geometric Ramsey theory problem* - 17:20 - 17:45 Tomasz Dzido,
*On some on-line Ramsey numbers* - 17:55 - 18:20 Przemysław Gordinowicz,
*A new approach to calculating small on-line Ramsey numbers for cliques* - 18:20 - 18:45 Krzysztof Krzywdziński,
*A new problem generalising the Ramsey number*

session 5B

- 16:30 - 16:55 Mindaugas Bloznelis,
*Degree and clustering in sparse intersection graphs* - 16:55 - 17:20 Katarzyna Rybarczyk,
*Independent sets in a random intersection graph* - 17:20 - 17:45 Valentas Kurauskas,
*Largest clique in sparse random intersection graphs* - 17:55 - 18:20 Arkadiusz Pawlik,
*Triangle-free intersection graphs of line segments with large chromatic number* - 18:20 - 18:45 Piotr Micek,
*Coloring intersection graphs of curves and arc-wise connected sets in the plane*

- 16:30 - 16:55 Halina Bielak,

- 16:30 - 18:55
19:00

*dinner*20:00

*open problems session*

Wednesday, September 19

8:00 - 9:00

*breakfast*9:00 - 10:00 Mathias Schacht,

*On the KLR conjecture in sparse random graphs*10:00 -10:30

*coffee*- 10:30-12:45
*contributed talks*(two paralell sessions 5+5; 10min break after 3rd talk) session 6A

- 10:30 - 10:55 Katarzyna Jesse-Józefczyk,
*Global security in graphs* - 10:55 - 11:20 Stephen Young,
*A Alon-Boppana result for the normalized Laplacian* - 11:20 -11:45 Leonid Plachta,
*Singular links and semicoloured planar bipartite graphs* - 11:55 - 12:20 Ekaterina Ponomarenko,
*On Borsuk’s and Nelson–Hadwiger’s problems for rational spaces* - 12:20 - 12:45 Vitaly Goldshteyn,
*The Borsuk and Gr”unbaum problems for (0, 1)- and (-1, 0, 1)-polyhedra in low dimensions*

session 6B

- 10:30 - 10:55 Milos Stojakovic,
*Winning fast in positional games on graphs* - 10:55 - 11:20 Małgorzata Bednarska-Bzdęga,
*On the relationship between Picker-Chooser and Maker-Breaker games* - 11:20 -11:45 Dennis Clemens,
*Fast strategies in Maker-Breaker games played on random boards* - 11:55 - 12:20 Mirjana Mikalački,
*Doubly biased Maker - Breaker Connectivity game* - 12:20 - 12:45 Walid Ben-Ameur,
*On graphs with unicyclic connected components*

- 10:30 - 10:55 Katarzyna Jesse-Józefczyk,

- 10:30-12:45
13:00

*lunch*14:30

*excursion*19:00

*banquet*

Thursday, September 20

8:00 - 9:00

*breakfast*9:00 - 10:00 Wojciech Szpankowski,

*Analytic combinatorics (of P. Flajolet): Profile of digital trees*10:00 - 10:30

*coffee*- 10:30 - 12:55
*contributed talks*(two paralell sessions 5+5; 10min break after 3rd talk) session 7A

- 10:30 - 10:55 Roman Glebov,
*On bounded degree spanning trees in the random graph process* - 10:55 - 11:20 Guillem Perarnau,
*Matchings in random biregular bipartite graphs* - 11:20 -11:45 Liudmila Ostroumova,
*The distribution of second degrees in preferential attachment models* - 11:55 - 12:20 Michał Jan Przykucki,
*Maximum percolation time in bootstrap percolation* - 12:20 - 12:45 Andrew Uzzell,
*The speed of bootstrap percolation*

session 7B

- 10:30 - 10:55 Małgorzata Sułkowska,
*The best choice problem for upward directed graphs* - 10:55 - 11:20 Codrut Grosu,
*On the rank of higher inclusion matrices* - 11:20 -11:45 Tomasz Krawczyk,
*Extending partial representations of function graphs and permutation graphs* - 11:55 - 12:20 Przemysław Krysztowiak,
*Recent progress on the jump number of interval orders* - 12:20 - 12:45 Harald Gropp,
*Configurations as graphs and hypergraphs*

- 10:30 - 10:55 Roman Glebov,

- 10:30 - 12:55
13:00

*lunch*- 14:15 - 15:55
*contributed talks*(two paralell sessions 4+4) session 8A

- 14:15 - 14:40 Artur Czumaj,
*Fast algorithms for finding cycles and trees in bounded degree graphs* - 14:40 - 15:05 Marko Savić,
*Linear time algorithm for optimal feed-link placement* - 15:05 - 15:30 Paweł Rzążewski,
*Beyond homothetic polygons: recognition and maximum clique* - 15:30 - 15:55 Konstanty Junosza-Szaniawski,
*Determining the L(2,1)-span in polynomial space*

session 8B

- 14:15 - 14:40 John Lapinskas,
*Optimal packings of edge-disjoint Hamilton cycles in graphs of high minimum degree* - 14:40 - 15:05 Katherine Staden,
*Approximate Hamilton decompositions of regular expanders* - 15:05 - 15:30 Allan Lo,
*Properly coloured Hamiltonian cycles in edge-coloured K_n* - 15:05 - 15:30 Fiachra Knox,
*Edge-disjoint Hamilton cycles in random graphs*

- 14:15 - 14:40 Artur Czumaj,

- 14:15 - 15:55
16:00 - 16:30

*coffee*- 16:30 - 18:55
*contributed talks*(two paralell sessions 5+5; 10min break after 3rd talk) session 9A

- 16:30 - 16:55 Olivier Baudon,
*On the structure of arbitrarily partitionable graphs with given connectivity* - 16:55 - 17:20 Julien Bensmail,
*On the size of graphs that can be partitioned under a given number of prescriptions* - 17:20 - 17:45 Radoslav Fulek,
*Hanani-Tutte for two clusters* - 17:55 - 18:20 Bartosz Walczak,
*Outerplanar graph drawings with few slopes* - 18:20 - 18:45 Katharina Jochemko,
*Arithmetic of marked order polytopes, monotone triangle reciprocity, and partial colorings*

session 9B

- 16:30 - 16:55 Balazs Patkos,
*On traces of set families* - 16:55 - 17:20 Sebastian Kieliszek,
*Turan numbers for forests with small components* - 17:20 - 17:45 Paulius Šarka,
*Large co-Sidon subsets in sets with a given additive energy* - 17:55 - 18:20 Maciej Ulas,
*Arithmetic properties of hyper k-ary partition function* - 18:20 - 18:45 Mahdi Amani,
*An ECO method for generating and enumerating AVL trees with n nodes*

- 16:30 - 16:55 Olivier Baudon,

- 16:30 - 18:55
19:00

*dinner*

Friday, September 21:

*tutorial day*- 8:00 - 9:00
*breakfast* - 9:00 - 10:40 Tibor Szabó,
*tutorial*,*Positional Games: The Neighborhood Conjecture and its neighborhood* - 10:40 - 11:10
*coffee* - 11:10 - 12:50 Łukasz Kowalik,
*tutorial*,*Algebraic approach to exact algorithms* - 13:00
*lunch* - 14:15 - 16:00 Tibor Szabó,
*lecture continued, exercises* - 16:00 - 16:30
*coffee* - 16:30 - 18:15 Łukasz Kowalik,
*lecture continued, exercises* - 18:30 - 19:30
*dinner* - 20:00 - 21:00 Tibor Szabó,
*solutions* - 21:00 - 22:00 Łukasz Kowalik,
*solutions*

- 8:00 - 9:00
Saturday, September 22:

*departure day*- 8:00 - 9:00
*breakfast*

- 8:00 - 9:00