Welcome to Combinatorics and Optimization

Title: On the relation among $\Delta$, $\chi$ and $\omega$

Abstract:I will present some work from my MMath thesis, which is on the relation among the maximum degree $\Delta(G)$, the chromatic number $\chi(G)$ and the clique number $\omega(G)$ of a graph $G$. In particular, we focus on two important and long-standing conjectures on this subject, the Borodin-Kostochka Conjecture and Reed's Conjecture. In 1977, Borodin and Kostochka conjectured that given a graph $G$ with $\Delta(G) \ge 9$, if $\chi(G) = \Delta(G)$, then $\omega(G) = \Delta(G)$. This is a step toward strengthening the well-known Brooks' Theorem. In 1998, Reed proposed a more general conjecture, which states that $\chi(G) \le \lceil \frac{1}{2} (\Delta(G)+\omega(G)+1) \rceil$ for any graph $G$.

In this talk, we show a weaker but more general Borodin-Kostochka-type result. That is, given a nonnegative integer $t$, for every graph $G$ with $\Delta(G) \ge 4t^2+11t+7$ and $\chi(G) = \Delta(G)-t$, the graph $G$ contains a clique of size $\Delta(G)-2t^2-7t-4$. We introduce the technique of Mozhan partitions and give a high-level overview of the proof. This generalizes some previous work on this topic. Then, we prove that both conjectures hold for odd-hole-free graphs. Lastly, we discuss a few constructions of classes of graphs for which Reed's Conjecture holds with equality, including a new family of irregular tight examples.

Title:Combinatorial rules for the geometry of Hessenberg varieties

progressions

 Abstract:

Hessenberg varieties were introduced by De Mari, Procesi, and Shayman in the early 1990s and lie at the intersection of geometry, representation theory, and combinatorics.  In 2012, Insko and Yong studied a class of Hessenberg varieties using patch ideals, a technique dating back to at least the 1970s from the study of Schubert varieties. In this talk, we will derive patch ideals and use them to study two classes of Hessenberg varieties.  We will see the combinatorics that govern the behaviour of these patch ideals and translate these results to the geometric setting. Based in part on work with Sergio Da Silva, Megumi Harada, and Jenna Rajchgot.

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

Title: Inapproximability of Sparsest Vector in a Real Subspace

Abstract:We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace (where sparsity refers to the number of nonzero entries). Formally we show that it is NP-Hard (under randomized reductions) to approximate the sparsest vector in a subspace within any constant factor. We recover as a corollary state of the art inapproximability factors for the shortest vector problem (SVP), a foundational problem in lattice based cryptography. Our proof is surprisingly simple, bypassing even the PCP theorem.

Our main motivation in this work is the development of inapproximability techniques for problems over the reals. Analytic variants of sparsest vector have connections to small set expansion, quantum separability and polynomial maximization over convex sets, all of which cause similar barriers to inapproximability. The approach we develop could lead to progress on the hardness of some of these problems.

Joint work with Euiwoong Lee.