Events

Title: Maximizing non-monotone submodular functions

Abstract:

Optimization of non-monotone submodular functions has applications in the maximum cut and maximum directed cut problems for graphs.

Title: A Quantum Query Complexity Trichotomy for Regular Languages

Abstract:

We consider the quantum query complexity of regular languages and discover a surprising trichotomy: each regular language has query complexity either Theta(1), ~Theta(sqrt(n)) or Theta(n). 

Title: Cospectral and strongly cospectral vertices

Abstract:

If $a$ is a vertex in a graph with adjacency matrix $A$, the \textsl{walk module} generated by $a$ is the $A$-invariant subspace spanned by the vectors $A^re_a$, for $r\ge0$.

Title: Two-colouring hypersurface complements in open Richardson varities

Abstract: 

Given an algebraic hypersurface $H \subset \mathbb{R}^n$, we can always 2-colour the components of the complement $\mathbb{R}^n \setminus H$ such that adjacent components are of opposite colours.

Title: Counting Pentagons in Triangle-free Binary Matroids

Abstract:

Every triangle-free graph with n vertices contains at most (n/5)^5 cycles of length five, and this value is attained by the balanced blowup of the 5-cycle.

Title: Circuit-hyperplane relaxation and matroid representation

Abstract:

Relaxing a circuit-hyperplane in a representable matroid can destroy representability.

Title: From weakly separated collections to matroid subdivisions

Abstract:

We study arrangements of slightly skewed tropical hyperplanes, called blades, on the vertices of a hypersimplex $\Delta_{k,n}$.

Title: Halfway to Rota's Basis Conjecture

Abstract:

Rota’s Basis Conjecture is that any rank-n matroid with n disjoint bases B_1, …, B_n has n disjoint transversal bases; a basis is transversal if it contains exactly one element from each B_i.

Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid

Abstract:

In 1978, it was shown that a natural greedy algorithm gives a 1/2 approximation to submodular maximization subject to a matroid constraint.

Title: The combinatorics of parametric Feynman integrals

Abstract:

Feynman integrals are used in perturbative quantum field theory to compute the probabilities of processes involving elementary particles. They can be represented as Feynman graphs and exhibit a rich combinatorial structure. The parametric representation of Feynman integrals is particularly suitable to be studied from a combinatorial perspective since it contains well known objects like the Kirchhoff polynomial.