Future students

Title: A characterization of (p,q)-mixing when p/q < 4

Abstract: Let Hom(G,H) be the graph whose vertex set is the set of H-colourings of G, and two H-colourings f and g are adjacent if f differs from g in at most one vertex.

Title: The Shapiro-Shapiro Conjecture

Abstract:

Given four lines in 3-space, can you find a fifth line that intersects the other four? How many?

This is the smallest non-trivial example of a "Schubert problem". The answer, in this case, is not hard to compute: there are two such lines. Generalizations of this fact date back to 19th century work of Schubert.

Title: Naji’s characterization of circle graphs

Abstract: A circle graph is the intersection graph of chords of a circle.

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.

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: 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: 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: Using Linear Algebra to do Matching Theory

Abstract:

A matching in a graph is a set of edges with each vertex contained in at most one edge. A perfect matching is a matching in which each vertex is contained in some edge.