CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Graph Homomorphisms
Organizer and Chair: Pavol Hell (SFU)

A first Intermediate class with limit object  [PDF]

We introduce a unifying approach to structural limits, covering both Lovasz et al. left limit and Benjamini-Schramm limit. It is known that limit objects can be described, in these cases, either by a graphon or by a graphing. We define a new kind of measurable relational structure, called "modeling".

Answering a question of Lovasz, we explicitly construct a limit object (a limit modeling) for a class intermediate between dense graphs and graphs with bounded degrees, namely the class of rooted trees with bounded height. From this, we derive an explicit limit modeling for converging sequences of graphs with bounded tree-depth.

LASZLO EGRI, Hungarian Academy of Sciences, Budapest
List H-Coloring a Graph by Removing Few Vertices  [PDF]

In the deletion version of the list homomorphism problem, we are given graphs $G$ and $H$, a list $L(v) \subseteq V (H)$ for each vertex $v \in V (G)$, and an integer $k$. The task is to decide whether there exists a set $W \subseteq V (G)$ of size at most $k$ such that there is a homomorphism from $G \setminus W$ to $H$ respecting the lists. We show that this problem is fixed-parameter tractable parameterized by $k$ and $|H|$. This is joint work with Rajesh Chitnis and Daniel Marx.

HAMED HATAMI, McGill University
The entropy of random-free graphons and properties  [PDF]

Every graphon defines a random graph on any given number $n$ of vertices. It was known that the graphon is random-free if and only if the entropy of this random graph is subquadratic. I will prove that for random-free graphons, this entropy can grow as fast as any subquadratic function. However, if the graphon belongs to the closure of a random-free graph property, then the entropy is $O(n \log n)$. This is based on a joint work with Sergey Norine.

JAROSLAV NESETRIL, Charles University
Tree-depth primer  [PDF]

The tree-depth of a graph G is the minimum height of a rooted forest, the closure of which contains G. This invariant (and close relatives) has been introduced in several contexts under different names. It is also related to the cycle rank of directed graphs and the star height of regular languages. We mention recently defined variants like schrub-depth, which presents several interesting problems.

We survey and analyze the properties of classes of graphs with bounded tree-depth, and study how these properties propagate via the so-called "low tree-depth decompositions" of sparse graphs (and structures).

ROBERT SAMAL, Charles University
Hedetniemi conjecture for strict vector chromatic number  [PDF] [SLIDES]

Hedetniemi in 1966 conjectured that chromatic number of a product of two graphs is equal to the minimum of the chromatic numbers of the two factors; the product is taken in the category of graphs with homomorphisms. We prove a variant of this where chromatic number is replaced by strict vector chromatic number, better known as $\vartheta(\bar G)$, the Lovász' theta function of the complement.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland