Future students

Title: The sparsest matroids omitting an independent flat

Abstract:

Given integers $k,r \ge 1$, what is the smallest a rank-$r$ matroid can be that does not contain a $k$-element independent set that is also a flat? I will answer this question, characterize the extremal examples, and draw parallels with a problem in graph theory.

Title: Submodular function maximization

Abstract:

I will give the introductory talk for this term's topic for the Combinatorial-Optimization Reading group, namely submodular function maximization. Submodular functions arise in diverse contexts in combinatorial optimization.

Title: When are two Schur functions the same?

Abstract: 

A pair of skew shapes are said to be (skew) equivalent if they admit the same number of semistandard tableaux of any weight; i.e. if their associated skew Schur functions are equal.

Title: Monochromatic cycle partitions

Abstract:

A classic result of Erdős, Gyárfás, and Pyber states that the vertex set of every complete graph, whose edges have been coloured with r colours, can be covered by r² log r disjoint monochromatic cycles.

Title: Polynomial Spaces

Abstract:

We describe some simple machinery that enables us to derive upper bounds on the size of codes, and lower bounds on the size of designs in a quite general setting.

Title: Combinatorial questions motivated by Invariant Theory

Abstract:

We begin the talk by discussing a question in Invariant Theory: given a representation $V$ of a Lie group $G$, when if the invariant ring $k[V]^G$ a polynomial ring? We give a conjectural answer which we have verified for $SL_n$ and discuss some combinatorial questions motivated by the proof. This is joint work with Dan Edidin.

Title: Signings and induced subgraphs of the Hypercube

Abstract:

Just over a month ago, Hao Haung resolved the sensitivity conjecture, a 30 year-old question about the complexity of boolean functions.

Title: Approximation Algorithms for Minimum-Norm Optimization Problems

Abstract:

In many optimization problems, a feasible solution induces a multidimensional cost vector. For example, in k-clustering, opening k facilities induces an assignment-cost vector indexed by the clients; in load-balancing, a schedule induces a load vector across the machines.

Title: Countable weighted graphs with no unfriendly partitions

Abstract: 

Title: Independence Polynomials and Their Roots

Abstract:

Independence polynomials are generating functions for the number of independent sets of each cardinality in a graph G.