The University College London (UCL) Combinatorics Seminar is held every Monday at 4–5pm during term time.

The venue for seminars this term is Room 346 at the SSEES Bulding, 14–16 Taviton Street.

To subscribe to the mailing list, please email Luke Collins on luke [dot] collins [dot] 22 [at] ucl [dot] ac [dot] uk.

Next Speaker

• 19th January 2026 - Dabeen Lee (Seoul National University)

  Binary polynomial optimization through the lens of binary matroids

  
  

  Combinatorial optimization is the problem of choosing an optimal combination of items from a discrete set of elements. One of the most pressing challenges in modern applications is to develop efficient methodologies for nonlinear combinatorial optimization. In this talk, we introduce a novel approach to solving nonlinear problems through the lens of boolean polynomials and binary matroids. Discovering connections to binary matroids, we develop a new framework for linearizing the equivalent boolean polynomial optimization formulation. We provide a simple characterization for the convex hull of binary solutions to the linearization when the underlying binary matroid is a projective geometry, which contains all binary matroids over the same ground set as restrictions. We also show that if the matroid satisfies the sums of circuits property, then the convex hull coincides with the associated cocycle polytope. Moreover, taking the signs of the objective coefficients into account, we extend the sums of circuits property to idealness of binary clutters via signed binary matroids.

  This talk is based on joint works with Ahmad Abdi (London School of Economics).