Future students

Title: The pathwidth theorem for induced subgraphs

Abstract: We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. If time permits , we will also try to discuss the proof of the first result mentioned above.

Based on joint work with Maria Chudnovsky and Sophie Spirkl.

Title: Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Abstract: What is the computational complexity of the greatest common divisor (GCD) of two univariate polynomials? The Euclidean algorithm provides a polynomial-time solution, and fast variants of the Euclidean algorithm can compute the GCD in nearly-linear time. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra, such as computing determinants and solving linear systems, can be performed in O(log^2 n) parallel time, and this can be used to compute the GCD in O(log^2 n) parallel time. This algorithm does not take advantage of any structure present in the resulting linear systems, so in principle one could compute the GCD in parallel even faster.

In this talk, I will describe a new algorithm that computes the GCD in O(log n) parallel time by using a combination of polynomial interpolation and Newton's identities for symmetric polynomials. In fact, this algorithm can be implemented as an arithmetic circuit of constant depth. Similar ideas yield constant-depth circuits to compute the resultant, Bézout coefficients, and squarefree decomposition.

Title: Minimum spectral radius in a given class of graphs

Abstract: :  In 1986, Brualdi and Solheid posed the question of determining the maximum and minimum spectral radius of a graph within a given class of simple graphs. Since then, this problem has been extensively studied for various graph classes. In this talk, I will discuss two such classes: simple connected graphs with a given order and size, and simple connected graphs with a given order and dissociation number. This presentation is based on joint works with Sebastian Cioaba, Dheer Noal Desai, and Celso Marques.  

Title: A O(log log m) prophet inequality for subadditive combinatorial auctions

Abstract:: I will present the paper "An O(log log m) prophet inequality for subadditive combinatorial auctions", by Dütting, Kesselheim, and Lucier. In the setting of online combinatorial auctions, we have a set of m items and n buyers. Buyers arrive one by one, and our goal is to irrevocably assign a set of items to each buyer as they arrive. An item can only be allocated to one buyer. Each buyer has a subadditive valuation function, which assigns a value to every possible subset of items that can be allocated to the buyer. Our goal is to maximize the social welfare of the final allocation, which is the sum of the valuations of the buyers. The paper provides a O(log log m) prophet inequality for this problem, beating the previous O(log m) barrier. This is the current best known polynomial time algorithm for this problem.

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. 

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: Induced subgraphs of graphs of large $K_{r}$-free chromatic number

Abstract:For an integer $r\geq 2$, the $K_{r}$-free chromatic number of a graph $G$, denoted by $\chi_{r}(G)$, is the minimum size of a partition of the set of vertices of $G$ into parts each of which induces a $K_{r}$-free graph. In this setting, the $K_{2}$-free chromatic number is the usual chromatic number. Which are the unavoidable induced subgraphs of graphs of large $K_{r}$-free chromatic number? Generalizing the notion of $\chi$-boundedness, we say that a hereditary class of graphs is $\chi_{r}$-bounded if there exists a function which provides an upper bound for the $K_{r}$-free chromatic number of each graph of the class in terms of the graph's clique number. With an emphasis on a generalization of the Gy\'arf\'as-Sumner conjecture for $\chi_{r}$-bounded classes of graphs and on polynomial $\chi$-boundedness, I will discuss some recent developments on $\chi_{r}$-boundedness and related open problems. Based on joint work with Mathieu Rundstr\"om and Sophie Spirkl.

Title:Coloring the integers while avoiding monochromatic arithmetic

progressions

 Abstract: Consider coloring the positive integers either red or blue one at a time in order.  Van der Waerden's classical theorem states that no matter how you color the integers, you will eventually have k equally spaced integers all colored the same for any k.  But, how can we minimize the number of times k equally spaced integers are colored the same?  Even for k = 3, this question is unsolved.  We will discuss progress towards proving an existing conjecture by leveraging a connection to coloring the continuous interval [0,1]. Our strategy relies on identifying classes of colorings with permutations and then using mixed integer linear programming.  Joint work with Jonathan Kariv and Noah Williams.

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

Title: Squares of eigenvalues and semi-definite optimization

Abstract: I will share some recent progress on two long-standing conjectures in spectral graph theory, namely the Elphick-Farber-Goldberg-Wocjan conjecture and the Bollob\'{a}s-Nikiforov conjecture. Both conjectures involve bounds on the sum of squares of the eigenvalues of a graph, and a key ingredient in our work is the interpretation of such sums as optimization problems involving semi-definite matrices. Part of the talk is joint work with Gabriel Coutinho and Thomás Jung Spier.