BrendanRooney

Archive of posts with tag 'BrendanRooney'

  • Brendan Rooney, Eigenpolytopes, Equitable Partitions, and EKR-type Theorems
    Eigenpolytopes, Equitable Partitions, and EKR-type Theorems
    Brendan Rooney
    Department of Mathematical Sciences, KAIST
    2017/4/24 Monday 5PM
    The Erdos-Ko-Rado Theorem is a classic result about intersecting families of sets. More recently, analogous “EKR-type” type theorems have been developed for other types of objects. For example, non-trivially intersecting vector spaces, and overlapping strings. In this seminar we will give a proof of the EKR Theorem for permutations in Sn due to Godsil and Meagher. Along the way we will see some useful tools from algebraic graph theory. Namely, a bound on the maximum size of an independent set in a graph, equitable partitions, and eigenpolytopes.
    Tags:

  • Brendan Rooney, Colourings, Vector Colourings and Cores
    Colourings, Vector Colourings and Cores
    Brendan Rooney
    Department of Mathematical Sciences, KAIST
    2015/10/28 Wed 5PM-6PM

    A k-colouring of a graph G is a partition of V(G) into k independent sets. The chromatic number χ(G) is defined as the smallest k so that G has a k-colouring. Alternatively, we can view colourings as homomorphisms to complete graphs, and define χ(G) to be the smallest k so that there is a homomorphism from G to Kk. The variants of χ(G) (for example, fractional chromatic number) are defined by replacing the complete graph Kk with a representative of a different class of graphs (for example, Kneser graphs).

    In this talk, we will consider the vector chromatic number of a graph. A vector colouring of a G is a map from V(G) to vectors in Rm (for some m). The goal is to map adjacent vertices to vectors that are far apart. We will look at representations of a graph on its least eigenspace as examples of vector colourings. For distance-regular graphs, these colourings are optimal. Furthermore, we give a method for determining if these colourings are unique. This leads to proofs that certain classes of distance-regular graphs are all cores.

    Tags:

Monthly Archives