Friday 20.12.2019 at 11:00 MI, room modrá posluchárna, Jan Grebík (Warwick University): Large deviation principles for graphons
Abstract: Sampling from any graphon W naturally induces a sequence of probability measures on the graphon space and it is a standard result that this sequence concentrates (in a precise sense) around W. Chatterjee and Varadhan proved that if W is a constant graphon, then the sequence satisfies a large deviation principle. I will review their result and discuss what happens for general graphon. This is joint work (in progress) with O.Pikhurko.
Friday 13.12.2019 at 10:00 MI, room modrá posluchárna, Yani Pehova (Warwick University): Characterization of quasirandom permutations by a pattern sum
Abstract: We say that a sequence
of permutations is quasirandom if, for each
and each ,
the probability that a uniformly chosen set
of entries of
induces
tends to
as
tends to infinity. It is known that a much weaker condition already forces
to be quasirandom; namely, if the above property holds for all .
We further weaken this condition by exhibiting sets ,
such that if a randomly chosen set
of entries of
induces an element of
with probability tending to ,
then
is quasirandom. Moreover, we are able to completely characterise the sets
with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight.
This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.
Friday 6.12.2019 at 10:00 ICS, room 318, Simón Piga (Universität Hamburg): Localised codegree conditions for Hamilton cycles in hypergraphs
Abstract: We study sufficient conditions for the existence of Hamiltonian cycles in uniformly dense uniform hypergraphs. Problems of this type were first considered by Lenz, Mubayi, and Mycroft for loose Hamiltonian cycles and AignerHorev and Levy considered it for tight Hamiltonian cycles for a fairly strong notion of uniformly dense hypergraphs. We focus on tight cycles and obtain optimal results for a weaker notion of uniformly dense hypergraphs. We show that if an vertex uniform hypergraph has the property that for any set of vertices and for any collection of pairs of vertices, the number of hyperedges composed by a pair belonging to and one vertex from is at least and has minimum vertex degree at least , then contains a tight Hamiltonian cycle. A probabilistic construction shows that the constant is optimal in this context. 
Friday 29.11.2019 at 10:00 ICS, room 318, Fiona Skerman (Bristol University): Random tree recursions: which fixed points correspond to tangible sets of trees?
Abstract:This talk focuses on tree automata on GaltonWatson trees. A tree automaton
is a finite set
of colours, and a map .
Each node receives a colour as a function of the colours of its children. Under the GaltonWatson branching process setup the probability that a node is coloured
is obtained as a fixed point of a system of equations. But this system need not have a unique fixed point. 
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 2coloring 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. 
Friday 25.10.2019 at 10:00 ICS, room 318, Jan Swart (Czech Academy of Sciences, UTIA): Frozen percolation on the 3regular 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 3regular 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 continuoustime binary Galton Watson tree that has
nice scale invariant properties. 
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 selfcontained otherwise. 
Friday 11.10.2019 at 10:00 ICS, room 318, Nicolás Sanhueza (Czech Academy of Sciences, ICS): Partitioning 2coloured complete 3graphs into two monochromatic tight cycles.
Abstract:
As a variant on the traditional Ramseytype questions, there has been a lot of research about the existence of spanning monochromatic subgraphs in complete edgecoloured 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 2edgecoloured complete graph can be partitioned into two monochromatic cycles of distinct colours. This was answered in the affirmative by Bessy and Thomassé in 2010. 
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 leftconvergence 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 cutdistance and prove counterparts
to the counting lemma, sampling lemma and inverse counting lemma. 
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.

Friday 13.9.2019 at 10:00 ICS, room 318, Václav Rozhoň (ETH): Derandomization of Distributed Graph Algorithms
Abstract: We present a simple polylogarithmictime deterministic distributed algorithm for network decomposition. This improves on a celebrated
time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and longstanding question in distributed graph algorithms. It also leads to the first polylogarithmictime deterministic distributed algorithms for numerous other problems, hence resolving several wellknown and decadesold 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. 
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 nowherezero 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. 
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 
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 towertype 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/ε. 
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ősSimonovits 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. 
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 Younglattice
Abstract: In this talk we will examine the local spectral measure of the Younglattice 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 n^{th} level the local spectral measure is absolutely continuous with respect to the Lebesguemeasure, 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 n^{th} symmetric group. In this talk we will examine the local spectral measure of the Younglattice 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 n^{th} level the local spectral measure is absolutely continuous with respect to the Lebesguemeasure, 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 n^{th} 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 ncube is a set that does not contain two distinct elements such that one is coordinatewise dominating the other. I will show that the Hausdorff dimension of an antichain is at most n1 and that its (n1)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 (n1)dimensional Hausdorff measure of an antichain is is less than or equal to the sum of the (n1)dimensional Hausdorff measures of its n orthogonal projections onto the facets of the unit ncube 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 