Combinatorial group

The Combinatorial Group of the Institute of Computer Science of the Czech Academy of Sciences organises a seminar in cooperation with the group Graph limits and inhomogeneous random graphs from the Institute of Mathematics of the Czech Academy of Sciences.

The seminars themselves are located either at the Institute of Mathematics, or at the Institute of Computer Science. Please check the location of each seminar!

We run also a reading group. For more info on this seminar, visit the reading group webpage.

Programme


Past seminars

Friday 24.1.2020 at 10:00 ICS, room 318, Tereza Klimošová (Charles University): Decomposing graphs into paths and trees

Abstract: Bensmail, Harutyunyan, Le and Thomassé conjectured that for a fixed tree T, the edge set of any graph G of size divisible by size of T with sufficiently high degree can be decomposed into disjoint copies of T, provided that G is sufficiently highly connected in terms of maximal degree of T. They proved the conjecture for trees of maximal degree 2 (i.e., paths). In particular, they showed that in the case of paths, the conjecture holds for 24-edge-connected graphs.
We improve this result showing that 3-edge-connectivity suffices, which is best possible. We disprove the conjecture for trees of maximum degree greater than two, prove the conjecture for certain forests and prove a relaxed version of the conjecture that concerns decomposing the edge set of a graph into disjoint copies of two fixed trees of coprime sizes.
Joint work with S. Thomassé.

Friday 17.1.2020 at 10:00 at 10:00 MI, room modrá posluchárna, Balázs Gerencsér (Hungarian Academy of Sciences): Decay of mutual information for factor of iid processes on the d-regular tree

Abstract: We review the concept of factor of iid processes that allows to capture the behavior of local algorithms on large networks. We investigate how much a global decision can or cannot be made using these processes. In particular, how much independent the output values need to be at far away vertices when applied on the limit case of the d-regular infinite tree.
Joint work with Viktor Harangi.

seminars in 2019

seminars in 2018

seminars in 2017

seminars in 2016