Seminar

Title: A Sudoku Baranyai's Theorem

Abstract: Motivated by constructing higher dimensional Sudokus we generalize the famous Baranyai's theorem. Let$n=\prod_{i=1}^d a_i$. Suppose that an $n\times\dots \times n$ ($d$ times) array $L$ is partitioned into$n/a_1\times\dots\times n/a_d$ sub‐arrays (called blocks). Can we color the $n^d$ cells of $L$ with $n^{d21}$ colors so that each layer (obtained by fixing one coordinate) and each $n/a_1\times\dots\times n/a_d$block contains each color exactly once? We generalize the well‐know theorem of Baranyai to answer this queestion. The case $d=2 a_1=a_2=3$ corresponds to the usual Sudoku. We also provide finite fieldconstruction of various related objects. This is joint work with Sho Suda.

Title: A hereditary generalization of Nordhaus-Gaddum graphs

Abstract: This talk will be an expanded version of the speaker's CanaDAM talk, the abstract of which is as follows:

Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph G and its complement is at most |G| + 1. The Nordhaus-Gaddum graphs are the class of graphs satisfying this inequality with equality, and are well-understood. In this paper we consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy that the sum of the chromatic numbers of H and its complement are at least |H|. We characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. We also discuss chi-boundedness and algorithmic results.

Title:Shifted Parking function

Abstract:Stanley recently introduced the shifted parking function symmetric function as a shifted analogue of the parking function symmetric function and posed the question of what the corresponding combinatorial objects are. This talk will answer that question and explain how the answer connects to projective representations of the symmetric group. Based on joint work with Zach Hamaker.

Title:A Toric Analogue for Greene's Rational Function of a Poset

Abstract: Given a finite poset, Greene introduced a rational function obtained by summing certain rational functions over the linear extensions of the poset. This function has interesting interpretations, and for certain families of posets, it simplifies surprisingly. In particular, Greene evaluated this rational function for strongly planar posets in his work on the Murnaghan–Nakayama formula. Develin, Macauley, and Reiner introduced toric posets, which combinatorially are equivalence classes of posets (or rather acyclic quivers) under the operation of flipping maximum elements into minimum elements and vice versa. In this work, we introduce a toric analogue of Greene's rational function for toric posets, and study its properties. In addition, we use toric posets to show that the Kleiss–Kuijf relations, which appear in scattering amplitudes, are equivalent to a specific instance of Greene's evaluation of his rational function for strongly planar posets. Also in this work, we give an algorithm for finding the set of toric total extensions of a toric poset.

Title:Regularity lemmas for hypergraphs of bounded VC dimension: improved bounds

Abstract:An important result at the interface of graph theory and logic is that graphs of bounded VC dimension have (small) homogeneous vertex-partitions, i.e., partitions where almost every pair of parts has density close to 0 or 1. Recently, Chernikov and Towsner proved a hypergraph generalization of this fact. The quantitative aspects of their result remain open. I will present some recent progress on this problem, answering two questions of Terry. This is a joint work with Asaf Shapira and Yuval Wigderson.

Title:Splitting algorithms for monotone inclusions with minimal dimension

Abstract: Many situations in convex optimization can be modeled as the problem of finding a zero of a monotone operator, which can be regarded as a generalization of the gradient of a differentiable convex function. In order to numerically address this monotone inclusion problem, it is vital to be able to exploit the inherent structure of the operator defining it. The algorithms in the family of the splitting methods achieve this by iteratively solving simpler subtasks that are defined by separately using some parts of the original problem.

In the first part of this talk, we will introduce some of the most relevant monotone inclusion problems and present their applications to optimization. Subsequently, we will draw our attention to a common anomaly that has persisted in the design of methods in this family: the dimension of the underlying space —which we denote as lifting— of the algorithms abnormally increases as the problem size grows. This has direct implications on the computational performance of the method as a result of the increase of memory requirements. In this framework, we characterize the minimal lifting that can be obtained by splitting algorithms adept at solving certain general monotone inclusions. Moreover, we present splitting methods matching these lifting bounds, and thus having minimal lifting.

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.

Title: Alice, Bob, and colours: An algebraic approach to quantum advantage

Abstract: Two-player one-round games exhibit quantum advantage if the availability of quantum resources results in non-classical correlations between the players' answers, which allow outperforming any classical strategy. The first part of the talk illustrates a link between (i) the occurrence of quantum advantage in a game, and (ii) the complexity of the corresponding classical computational problem. In particular, I will show that both (i) and (ii) are determined by the same algebraic invariants of the game, known as polymorphisms. This allows transferring methods from the universal-algebraic theory of constraint satisfaction to the setting of quantum advantage. In particular, this approach yields a complete characterisation of the occurrence of quantum advantage for games played on graphs.   

The second part of the talk outlines recent work on the quantum chromatic number introduced in [Cameron--Montanaro--Newman--Severini--Winter'07]. The gap between this parameter and its classical counterpart is a measure of quantum advantage for the graph colouring game. Using the polymorphic approach, I will show that the maximum gap is linear when the quantum chromatic number makes use of entangled strategies on a constant number of qubits. In contrast, in the case of unlimited entanglement resources, I will prove the existence of graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large, conditional to the quantum variants of Khot's d-to-1 Conjecture [Khot'02] and Håstad's inapproximability of linear equations [Håstad'01].

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 1:30pm,

Title: Random analogues of Erd\H{o}s-Ko-Rado type results.

Abstract: The classical Erd\H{o}s-Ko-Rado (EKR) theorem and its variants can be translated into characterizing maximum co-cliques of graphs in Association schemes. For instance, the classical Erd\H{o}s-Ko-Rado characterizes maximum co-cliques in the Kneser graph. Given a graph $G$, by $G_{p}$, we denote the random subgraph of $G$ in which edges appear independently, each with a probability $p$. In this talk, we consider the following question: for which probabilities is the independence number of $G_{p}$ equal to that of $G$? Bollabas-Narayanan-Raigorodskii investigated the independence numbers of random subgraphs of the Kneser graph. In this talk, we will investigate the independence numbers of random subgraphs of (i) the derangement graph on permutations; and (ii) the perfect matching graphs. The derangement graph is associated with the EKR type result on permutations and the perfect matching graph is associated with EKR type result on perfect matchings. This is joint work with the members of the PIMS Collaborative Research Group on Movement and Symmetry in graphs.