Events

Abstract: A $k$-sunflower is a family of $k$ distinct sets whose pairwise intersections all coincide. The Erd\H{o}s--Szemer\'edi conjecture asserts that for every $k \ge 3$ there is a constant $c_k < 2$ such that any $k$-sunflower-free family $\mathcal{F} \subseteq 2^{[n]}$ satisfies $|\mathcal{F}| \le c_k^{\,n}$. Bucic, He, and Lee recently proved this with an explicit bound.

In this talk we survey the problem and its place among sunflower questions, then work through the proof, centered on a vector-sunflower argument. We also discuss how the result relates to a related problem, the uniform Erd\H{o}s--Rado conjecture, which it does not settle. No prior background is assumed. 

Abstract: Determining whether a graph is k-colourable is a famously hard computational problem. Even when placing significant restrictions on the graph, the resulting problem is often NP-hard. In this talk, we focus on the case of restricting the diameter. Under the Exponential Time Hypothesis, there does not exist a sub-exponential algorithm for 3-colouring diameter-4 graphs or for 4-colouring diameter-2 graphs. Hence, the interesting remaining cases are 3-colouring graphs of diameter 2 or 3. We show that 3-colouring diameter-3 graphs can be solved in 2^O(n^{2/3−ε}) for any ε < 1/33 by providing an algorithm based on a structural result. This improves on the previous best known algorithm due to Dębski, Piecyk and Rzążewski.

This talk is based on joint work with Carla Groenland and Sophie Spirkl.

Abstract: Having seen the BB84 quantum key distribution protocol last week, this week we’ll see what it means for QKD to be secure, following the basic principle that “information gain implies disturbance”. We’ll talk about what authentication is needed for QKD’s security guarantees to hold, and other factors like device security and finite key effects.

Abstract: We study the H-chromatic symmetric functions X_G^H introduced by Eagles et al. (2022), which generalizes the chromatic symmetric function X_G to the context of H-colorings, which tracks graph homomorphisms G → H. We first show that self-chromatic symmetric functions X_G^G determine quantities like the connected components of a forest and the degree sequence of a caterpillar. We then show that the X_G^H's form a basis of the symmetric function ring for certain collections of (G,H), such as the self-CSFs of complete multipartite graphs. Lastly, we define and discuss H-chromatic polynomials as specializations of H-CSFs. This is joint work with Laura Pierson.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.

Abstract: A 0-1 matrix M is perfect if the polyhedron {x ≥ 0 : Mx ≤ 1} is integral. Perfect matrices are closely related to perfect graphs and have several remarkable properties. In particular, perfectness is equivalent to total dual integrality, and perfect matrices admit an excluded-minor characterization.

A 0-1 matrix M is ideal if the polyhedron {x ≥ 0 : Mx ≥ 1} is integral. Unlike perfect matrices, ideal matrices do not correspond to a single well-understood class of combinatorial objects. In this talk, we will explore which of the remarkable properties of perfect matrices have counterparts for ideal matrices. We will discuss what is known, what fails, and some of the intriguing open questions that arise from this comparison.