|16h00||Open Problem Session|
In this talk we will look at posets and their dimension through the lens of the Nesetril-Ossona de Mendez theory of sparsity for graphs. The type of questions studied here are of the following form: Given some fixed sparse class of graphs, is it true that posets whose cover graphs are in the class have dimension bounded in terms of their height? This is the case for instance for planar graphs, as shown by Streib and Trotter. There has been a flurry of positive results in that direction recently, including classes with bounded treewidth, bounded genus, and more generally excluding a fixed minor. I will first give an introduction to this area, assuming no background knowledge on posets. Then I will sketch a proof that the above property holds more generally for every class with bounded expansion, a result obtained jointly with Piotr Micek and Veit Wiechert. This is in a sense best possible, as it cannot be extended to nowhere dense classes; in fact, it already fails for classes with locally bounded treewidth.
If G is a graph with large chromatic number, then what can we say about its induced subgraphs? It is possible that G has a large clique, but if this is not the case then are there other subgraphs that must appear? For instance, can we say something about the the set of lengths of induced cycles in G? Some thirty years ago, Gyarfas made a sequence of conjectures concerning induced cycles in graphs of large chromatic number. Recently, there has been progress on these conjectures in work of Maria Chudnovsky, Paul Seymour and the speaker; there has also been a breakthrough by Marthe Bonamy, Pierre Charbit and Stephan Thomasse on a closely related problem. We will discuss these results, and mention some new developments.
I want to speak about two recent results:
We say that a sequence of d-regular graphs is "essentially expander" if it can be turned into a disjoint union of expanders by removing and adding o(n) edges. We give a spectral characterization of such sequences. (Essential) expansion is not testable by randomly sampling a constant number of vertices and looking at a ball of constant radius centered at these vertices. Indeed, graphs with large girth may be essential expanders or very far from essential expanders. However, there exists local (Benjamin-Schramm) statistics that a sequence with this statistics is essentially expander, i.e., essential expansion is locally forceable as showed by the next result: We solve Bowen's problem proving that the local (sofic) approximation of a finitely generated group with Kazhdan Property (T) is essentially expander. Our results extend to the strongly ergodic case and give a non-separable(!) ergodic decomposition theorem (for ultraproducts). We use our characterization to give an alternative construction of non- hyperfinite 2-dimensional simplicial complexes (in the sense of Freedman and Hastings). The talk will focus on the graph theoretical parts, no background will be assumed in group theory and ergodic theory.
The recently emerged theory of combinatorial limits has opened new links between analysis, combinatorics, computer science, group theory and probability theory. Combinatorial limits give an analytic way of representing large discrete objects. This talk will be focused on limits of permutations and graphs that are uniquely determined by finitely many constraints. We will explore the relation of such limits to quasirandomness of graphs and permutations and answer a question of Graham (2004) on quasirandom permutations. Motivated by applications in extremal combinatorics, Lovasz and Szegedy (2011) conjectured that the space of typical vertices of every finitely forcible graph limit must be compact and have finite dimension. We provide counterexamples using a new method for constructing finitely forcible combinatorial limits we developed. We finish by a discussion of the relation of our results to weak regularity partitions.