Abstract: An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. There are several known criteria that guarantee the existence of an IT, of the following general form: the graph G has an IT unless the subgraph G_s of G, induced by the union of some subset S of vertex classes, has a small dominating set. These criteria have been used over the years to solve many combinatorial problems.
The known proofs of these IT theorems do not give efficient algorithms for actually finding an IT or a subset S of classes such that G_s has a small dominating set. Here we present appropriate weakenings of such results that do have effective proofs. These result in algorithmic versions of many of the original applications of IT theorems. We will discuss a few of these here, including hitting sets for maximum cliques, circular edge-coloring of bridgeless cubic graphs, and hypergraph matching problems.

[Slides]

Abstract: What does it mean for a structure to be sparse or dense? What is the point of differentiating between sparse and dense structures? Is there an objective and essential boundary between sparse and dense structures? The aim of this talk is to address, at least partially, these questions, from the points of view of model theory, structural graph theory, and theoretical computer science.

[Slides]