Welcome to Combinatorics and Optimization

Title: Learning from Coarse Samples

Abstract:Coarsening occurs when the exact value of a sample is not observed.
Instead, only a subset of the sample space containing the exact value is known.
Coarse data naturally arises in diverse fields, including Economics, Engineering, Medical and Biological Sciences, and all areas of the Physical Sciences.
One of the simplest forms of coarsening is rounding, where data values are mapped to the nearest point on a specified lattice.

We survey applications of coarse learning to regression with self-selection bias, regression with second-price auction data, and present details of an SGD-based algorithm for coarse Gaussian mean estimation.

Based on joint work with Alkis Kalavasis and Anay Mehrotra (https://arxiv.org/abs/2504.07133)

Title:Source characterization of the hypegraphic posets

Abstract: For a hypergraph $\mathbb{H}$ on $[n]$, the hypergraphic poset $P_\mathbb{H}$ is the transitive closure of the oriented $1$-skeleton of the hypergraphic polytope $\Delta_\mathbb{H}$, which is the Minkowski sum of the standard simplices $\Delta_H$ for each hyperedge $H \in \mathbb{H}$. In 2019, C. Benedetti, N. Bergeron, and J. Machacek established a remarkable correspondence between the transitive closure of the oriented $1$-skeleton of $\Delta_\mathbb{H}$ and the flip graph on acyclic orientations of $\mathbb{H}$. Viewing an orientation of $\mathbb{H}$ as a map $A$ from $\mathbb{H}$ to $[n]$, we define the sources of the acyclic orientations as the values $A(H)$ for each hyperedge $H \in \mathbb{H}$. In a recent paper, N. Bergeron and V.

Pilaud provided a characterization of $P_\mathbb{H}$ based on the sources of acyclic orientations for interval hypergraphs. Specifically, two distinct acyclic orientations $A$ and $B$ of $\mathbb{H}$ are comparable in $P_\mathbb{H}$ if and only if their sources satisfy $A(H) \leq B(H)$ for all hyperedges $H\in \HH$. The goal of this work is to extend this source characterization of $P_\mathbb{H}$ to arbitrary hypergraphs on $[n]$.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:Constraining moduli space cohomology by counting graphs

Abstract: In 1992, Kontsevich defined complexes spanned by graphs. These 
complexes are increasingly prominent in algebraic topology, geometric 
group theory and mathematical physics. For instance, a 2021 theorem by 
Chan-Galatius and Payne implies that the top-weight cohomology of the 
moduli space of curves of genus g is equal to the homology of a specific 
graph complex. I will present a new theorem on the asymptotic growth 
rate of the Euler characteristic of this graph complex and explain its 
implication on the cohomology of the moduli space of curves. The proof 
involves solving a specific graph counting problem.