Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width
Zoom ID: 869 4632 6610 (ibsdimag)The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence
10 events found.
Seminars and Colloquiums
Boram Park (박보람), Odd coloring of sparse graphs
Room B232 IBS (기초과학연구원)We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph
Michael Savery, Induced subgraphs of induced subgraphs of large chromatic number
Zoom ID: 869 4632 6610 (ibsdimag)We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that …
Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems
Room B332 IBS (기초과학연구원)In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid
Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs
Room B332 IBS (기초과학연구원)The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph …
Andreas Holmsen, A colorful version of the Goodman-Pollack-Wenger transversal theorem
Room B332 IBS (기초과학연구원)Hadwiger's transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently …
Jan Kurkofka, Canonical Graph Decompositions via Coverings
Zoom ID: 869 4632 6610 (ibsdimag)We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. …
Gil Kalai, The Cascade Conjecture and other Helly-type Problems
Zoom ID: 868 7549 9085For a set
Stijn Cambie, The precise diameter of reconfiguration graphs
Room B332 IBS (기초과학연구원)Reconfiguration is about changing instances in small steps. For example, one can perform certain moves on a Rubik's cube, each of them changing its configuration a bit. In this case, …
Sebastian Siebertz, Transducing paths in graph classes with unbounded shrubdepth
Zoom ID: 869 4632 6610 (ibsdimag)Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a …