PACM Colloquium: Matija Bucic, Mathematics, Princeton University

*This event is in-person and open only to Princeton University ID holders

  Two classical decomposition problems

Abstract: Decomposition problems make one of the most classical classes of combinatorial questions with many connections and applications to other fields. In this talk I will discuss recent progress on two classical conjectures in the area, namely Rota's basis conjecture and the Erd\H{o}s-Gallai conjecture.

Rota's basis conjecture in a simplified form asserts that given $n$ disjoint bases in a vector space of dimension $n$ we can decompose the elements making the bases into $n$ so called transversal bases, namely bases which intersect each original basis in exactly one element. This conjecture has attracted a lot of attention over the years due to its numerous connections to other topics and in particular recently when it was the subject of the 12th Polymath project. In its full generality the conjecture extends to the setting of matroids, important algebraic objects generalizing the notion of vector spaces.

The Erd\H{o}s-Gallai conjecture dating back to the 1960s is one of the most classical conjectures in the area of graph decomposition problems and has attracted a lot of attention over the years. It asserts that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. Based on joint work with Kwan, Pokrovskiy and Sudakov and Montgomery.

^{Bio: Matija Bucic is a mathematician working on problems in extremal and probabilistic combinatorics. He completed his Ph.D. in Discrete Mathematics on Local to global phenomenon and other topics in probabilistic and extremal combinatorics at ETH Zürich in 2021. He is currently a Veblen Research Instructor, a joint position between Princeton University and Institute for Advanced Study.}