We organise 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 14.6.2019 at 10:00 MI, Fiona Skerman (Masaryk University): Random tree recursions: which fixed points correspond to tangible sets of trees?
Abstract:This talk focuses on tree automata on Galton-Watson trees. A tree automaton A 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 Galton-Watson branching process set-up 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.
The tree automaton colours locally; it assigns a colour to each node based on the colours of its child nodes. But can we colour each node v looking only at the uncoloured structure rooted at v in such a way that the resultant colouring 'agrees' with the tree automaton at a fixed point? I shall formally define this global colouring, interpretation, and provide a nearly complete description of necessary and sufficient conditions for a fixed point to not admit an interpretation, in which case it is called rogue. The inspiration for this work came from the branching process methods to study the 2-core of a random graph.
Joint work with Tobias Johnson and Moumanti Podder. (https://arxiv.org/abs/1808.03019)
Friday 21.6.2019 at 10:00 MI, room modrá posluchárna, Andrew Goodall (Charles Unversity): 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 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.
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