4th 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
  • 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
    • 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
    • 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
    • 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
    • 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
    • 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
    • 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
    • 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
    • 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
    • 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
    • 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
  • Saturday, September 22: departure day

    • 8:00 - 9:00 breakfast