Events

Title: Density and Structure of Homomorphism-Critical Graphs

Abstract: 

Let H be a graph. A graph G is H-critical if every proper subgraph of G admits a homomor-
phism to H, but G itself does not.

Title: Claw-free matroids

Abstract: A simple binary matroid is claw-free if it has no independent rank-3 flat. I will discuss a structure theorem, obtained jointly with Kazuhiro Nomoto, that classifies these objects exactly.

Title: Acyclic Colouring of Graphs on Surfaces

Abstract: An acyclic k-colouring of a graph G is a proper k-colouring of G with no

Title: Algorithms for Rank-1 Bimatrix Games

Abstract:

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices.

Title: The geometry of matroids

Abstract:

Matroid theory is a combinatorial theory of independence which has its origins in linear algebra and graph theory, and turns out to have deep connections with many other fields.

Title: Counting Partitions Inside a Rectangle

Abstract:

The study of integer partitions is a classic subject with applications ranging from number theory to representation theory and combinatorics.

Title: The smallest eigenvalues of Hamming, Johnson and other graphs

Abstract:

The smallest eigenvalue of graphs is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut.

Title: Entropy and enumeration

Abstract: The information-theoretic concept of entropy is closely related to enumeration;

Title: Science of Security-- Could Such a Thing Exist?

Abstract: Recent years have seen increasing calls to make security research more "scientific". Who can argue with science being desirable?

Title: Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold 

Abstract:

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree Δ is rapidly mixing for k ≥ Δ+2.