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!


Friday 29.11.2019 at 10:00 ICS, room 318, Fiona Skerman (Masaryk University): TBA

Friday 6.12.2019 at 10:00 ICS, room 318, Simón Piga (Universität Hamburg):TBA

Friday 17.1.2020 at 10:00, 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.

Past seminars

Friday 8.11.2019 at 100:00 MI, room modrá posluchárna, Martin Balko (Charles University): On ordered Ramsey numbers

Abstract: An ordered graph is a graph together with a total ordering on its vertex set. The ordered Ramsey number of an ordered graph is the minimum such that every 2-coloring of the edges of the ordered complete graph on vertices contains a copy of as an ordered subgraph. In this talk we survey recent results about ordered Ramsey numbers, emphasize the differences from the standard Ramsey numbers, and list some of the open problems in this relatively new area.
This talk is based on joint works with J. Cibulka, K. Král, and J. Kynčl and with V. Jelínek and P. Valtr.

Friday 25.10.2019 at 10:00 ICS, room 318, Jan Swart (Czech Academy of Sciences, UTIA): Frozen percolation on the 3-regular tree

Abstract: In frozen percolation, i.i.d. uniformly distributed activation times are assigned to the edges of a graph. At its assigned time, an edge opens provided neither of its endvertices is part of an infinite open cluster; in the opposite case, it freezes. Aldous (2000) showed that such a process can be constructed on the infinite 3-regular tree and asked whether the event that a given edge freezes is a measurable function of the activation times assigned to all edges. We give a negative answer to this question, or, using an equivalent formulation and terminology introduced by Aldous and Bandyopadhyay (2005), we show that the recursive tree process associated with frozen percolation on the oriented binary tree is nonendogenous. An essential role in our proofs is played by a frozen percolation process on a continuous-time binary Galton Watson tree that has nice scale invariant properties.
Joint work with Balázs Ráth and Tamás Terpai.

Friday 18.10.2019 at 10:00 MI, room modrá posluchárna, Jan Hladký (Czech Academy of Sciences, MI): Graph norms

Abstract: The space of graphons can be regarded as a (subset of) several Banach spaces, for example by taking the norm to be the L1 or the cut norm. There is an interesting class of norms coming from subgraph densities. This talk will be an introduction to this emerging field. I will present some classical applications of graph norms to extremal graph theory, and time permitting, I will mention some work we recently did with Frederik Garbe, Joonkyung Lee and Bjarne Schülke. I will assume familiarity with graphons in case people are ok with that, and make the talk self-contained otherwise.

Friday 11.10.2019 at 10:00 ICS, room 318, Nicolás Sanhueza (Czech Academy of Sciences, ICS): Partitioning 2-coloured complete 3-graphs into two monochromatic tight cycles.

Abstract: As a variant on the traditional Ramsey-type questions, there has been a lot of research about the existence of spanning monochromatic subgraphs in complete edge-coloured graphs and hypergraphs. One of the central questions in this area was proposed by Lehel around 1979, who conjectured that the vertex set of every 2-edge-coloured complete graph can be partitioned into two monochromatic cycles of distinct colours. This was answered in the affirmative by Bessy and Thomassé in 2010.
We generalise the question of Lehel to the setting of 3-uniform hypergraphs (3-graphs). More precisely, we show that every sufficiently large 2-edge-coloured complete 3-graph admits a vertex partition into two monochromatic tight cycles, possibly of the same colour. We also present examples showing that (in contrast to the graph case) it is not always possible to find partitions into two monochromatic tight cycles of different colours. As by-products from our proof, we can find vertex partitions into two cycles of different colours and two vertices, and vertex partitions into a cycle and a path of different colours.
This is joint work with Frederik Garbe, Richard Mycroft, Richard Lang and Allan Lo.

Friday 4.10.2019 at 10:00 ICS, room 318, Frederik Garbe (Czech Academy of Sciences, MI): Limits of Sequences of Latin Squares

Abstract: We introduce a limit theory for sequences of Latin squares paralleling the ones for dense graphs and permutations. The limit objects are certain distribution valued two variable functions, which we call Latinons, and left-convergence is defined via densities of kxk subpatterns of Latin Squares. The main result is a compactness theorem stating that every sequence of Latin squares of growing orders has a Latinon as an accumulation point. Furthermore, our space of Latinons is minimal, as we show that every Latinon can be approximated by Latin squares. This relies on a result of Keevash about combinatorial designs. We also introduce an analogue of the cut-distance and prove counterparts to the counting lemma, sampling lemma and inverse counting lemma.
This is joint work with R. Hancock, J. Hladky, and M. Sharifzadeh.

Friday 27.9.2019 at 10:00 ICS, room 318, Tamás Mészáros (Freie Universität Berlin): Greedy maximal independent sets via local limits

Abstract: The greedy algorithm for finding a maximal independent set in a graph on vertices can be described as follows. Let be a permutation of chosen uniformly at random. Starting from an empty set , at step add to the set if and only if is an independent set in . This very natural algorithm has been studied extensively in various settings in combinatorics, probability, computer science -- and even in chemistry. In this talk we present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to study new ones, such as random trees.
Joint work with Michael Krivelevich, Peleg Michaeli and Clara Shikhelman

Friday 13.9.2019 at 10:00 ICS, room 318, Václav Rozhoň (ETH): Derandomization of Distributed Graph Algorithms

Abstract: We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated -time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87; SICOMP'92]---which had been called the most outstanding problem in the area.
The main implication is a more general distributed derandomization theorem: Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that - = -. That is, for any distributed problem whose solution can be checked deterministically in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. Informally, for the standard first-order interpretation of efficiency as polylogarithmic-time, distributed algorithms do not need randomness for efficiency.
By known connections, our result leads also to substantially faster randomized algorithms for a number of well-studied problems including -coloring, maximal independent set, and Lovász Local Lemma.
Joint work with Mohsen Ghaffari

Friday 21.6.2019 at 10:00 ICS, room 318, Andrew Goodall (Charles University): The canonical Tutte polynomial for signed graphs

Abstract:The "trivariate Tutte polynomial" of a signed graph contains among its evaluations both the number of proper colorings (enumerated by Zaslavsky) and the number of nowhere-zero flows (only recently enumerated by Qian and independently by Goodall, Litjens, Regts and Vena). In this, the trivariate Tutte polynomial parallels the Tutte polynomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations, and the resemblances do not end there.
I aim to sketch the notions of signed graphs and their colorings and flows, introduce the trivariate Tutte polynomial by its subset expansion, explain the "Recipe Theorem" for deletion-contraction invariants of signed graphs, and use this to give an elementary proof of the enumerations of signed graph colorings and flows. For those familiar with the Tutte polynomial, all these steps are clear parallels to the case of graphs; for those not so familiar, the talk never strays beyond the confines of self-containment - but hopefully a smidgen beyond self-evidence.

Friday 7.6.2019 at 10:00 ICS, room 318 Israel Rocha (Czech Academy of Sciences, ICS): Partial sum of eigenvalues of random graphs

Abstract: In this talk we present new results on the partial sum of eigenvalues of the two main matrices in SGT: adjacency and Laplacian. Given a matrix M with eigenvalues . We define the partial sum

for . This parameter has its origens in theoretical chemistry in the Hückel molecular orbital theory. In this theory the behavior of the so-called -electrons in an unsaturated conjugated molecule is fully described in terms of the eigenvalues of the corresponding adjacency matrix. This parameter has been extensively investigated for several different matrices. Here, we present new upper bounds for for the Laplacian and adjacency matrix of random graphs.

Friday 10.5.2019 at 10:00 MI, room modrá posluchárna, Fan Wei (Stanford Unversity): Fast Permutation Property Testing

Abstract: Szemerédi's regularity lemma is an important and powerful tool in graph theory. Although the regularity lemma is powerful, a notable drawback is that applications of the regularity lemma will result in very weak quantitative estimates. One important application of the regularity lemma is the field of property testing, whose goal is to very quickly distinguish between objects that stratify a certain property from those that are ε-far from satisfying that property. Some of the most general results in this area give "constant query complexity" algorithms, which means the amount of information it looks at is independent of the input size. These results are proved using regularity lemmas or graph limits. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, of tower-type or worse, as a function of 1/ε, making them impractical. We show by entirely new methods that for testing hereditary permutations properties, such general results still hold with query complexity only polynomial in 1/ε.
This is a joint work with Jacob Fox.

Friday 5.4.2019 at 10:00 MI, room modrá posluchárna, Joonkyung Lee (University of Hamburg): Recent progress in Sidorenko's conjecture

Abstract: A celebrated conjecture of Sidorenko and Erdős-Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs.
In this talk, I will give an overview of some recent progress in Sidorenko's conjecture and related topics, and explain various tools developed to attack the conjecture. In particular, an information theoretic approach and a group theoretic approach will be discussed. Based on joint work with David Conlon, Jeong Han Kim, and Choongbum Lee.

Friday 1.3.2019 at 10:00 MI, room modrá posluchárna by Ferenc Bencs (Central European University and Hungarian Academy of Sciences): Local spectral measures of the Young-lattice

Abstract: In this talk we will examine the local spectral measure of the Young-lattice as a graph, that is a graph on the irreducible representation of all the symmetric groups. This graph has been thoroughly investigated and it was observed by Stanley, that the local spectral measure of the vertex corresponding to the empty partition is the normal distribution. Building on these techniques, we will show that from any vertex of the nth level the local spectral measure is absolutely continuous with respect to the Lebesgue-measure, moreover, its density function is a "polynomial perturbation" of the density function of the normal distribution, where the polynomial depends only on the character table of the nth symmetric group. In this talk we will examine the local spectral measure of the Young-lattice as a graph, that is a graph on the irreducible representation of all the symmetric groups. This graph has been thoroughly investigated and it was observed by Stanley, that the local spectral measure of the vertex corresponding to the empty partition is the normal distribution. Building on these techniques, we will show that from any vertex of the nth level the local spectral measure is absolutely continuous with respect to the Lebesgue-measure, moreover, its density function is a "polynomial perturbation" of the density function of the normal distribution, where the polynomial depends only on the character table of the nth symmetric group.

Friday 15.2.2019 at 10:00 MI, room modrá posluchárna: Christos Pelekis (Czech Academy of Sciences): Projection inequalities for antichains

Abstract: An antichain in the unit n-cube is a set that does not contain two distinct elements such that one is coordinate-wise dominating the other. I will show that the Hausdorff dimension of an antichain is at most n-1 and that its (n-1)-dimensional Hausdorff measure is at most n. Both bounds are best possible, and the latter is obtained as a corollary of the following statement, which may be of independent interest: the (n-1)-dimensional Hausdorff measure of an antichain is is less than or equal to the sum of the (n-1)-dimensional Hausdorff measures of its n orthogonal projections onto the facets of the unit n-cube containing the origin. This is joint work with Konrad Engel, Themis Mitsis and Christian Reiher.

Friday 25.1.2019 at 10:00 MI, room "modrá posluchárna": Mate Vizer (Hungarian Academy of Sciences): Geometry of permutation limits

Abstract: We initiate a limit theory of permutation valued processes, building on the recent theory of permutons. We apply this to study the asymptotic behaviour of random sorting networks. Despite main conjectures concerning random sorting networks were recently solved, the techniques developed might be independent of interest. Joint work with M. Rahman and B. Virag

seminars in 2018

seminars in 2017

seminars in 2016