Seminar

Title: Bivariate P-polynomial Association Schemes on the Fibers of Uniform Posets

Abstract: Orthogonal polynomials emerging in the context of P- and Q-polynomial association schemes are known to reside within the Askey-scheme. This relationship forms a bridge between algebraic combinatorics and the study of special functions, yielding significant benefits for both fields. Recent research has introduced multivariate generalizations of P- and Q-polynomial association schemes and provided numerous examples. This development aims notably to deepen our understanding of multivariate analogues of Askey-Wilson polynomials. In this talk, we will review this generalization, its connection to m-distance-regular graphs, and an algebraic combinatorial structure known as a "uniform poset," from which many examples of bivariate schemes appear to originate.

Title: Intersections of graphs and χ-boundedness: characterizing χ-guarding graph classes

Abstract: For two graphs G1, G2, their intersection is given by only keeping the vertices and edges that appear in both. This graph operation is closely related to various intersection graph classes, such as the intersection graphs of axis-aligned rectangles. We are interested in the interplay between the graph intersection operation and χ-boundedness. A graph class C  is χ-bounded if there exists a function providing an upper bound for the chromatic number of each graph in the class based on the graph’s clique number.

Title: Tight bounds for reconstructing graphs from distance queries

Abstract: Suppose you are given the vertex set of a graph and you want to discover the edge set. An oracle can tell you, given two vertices, what the distance is between these vertices in the graph. (For example, in a computer network, this would represent the minimum number of communication links needed to send a message from one computer to another.) Based on the answer, you may select the next query. The (labelled) graph is reconstructed when there is a single edge set compatible with the answers. How many queries are needed, in the worst case? The question becomes interesting for bounded degree graphs. We provide tight bounds for various classes of graphs, improving both the lower and upper bound, in both the randomized and deterministic setting. 

Title: Two variations of the chromatic symmetric function

Abstract: The /chromatic symmetric function/ is a symmetric function generalization of the chromatic polynomial that encodes the ways to color a graph such that no two adjacent vertices get the same color. We will discuss two different analogues of the chromatic symmetric function: a K-theoretic analogue called the /Kromatic symmetric function/, and a categorification called the /chromatic symmetric homology/. We show that certain properties of a graph can be recovered given its Kromatic symmetric function, and we give some formulas for special cases of the chromatic symmetric homology.

Title: Approximating Graphic TSP with matchings

Abstract: Revisiting defining character of the field of algorithm design and complexity, TSP!. While the problem itself is NP-Hard and difficult to approximate, various formulations, such as the Metric version, have yielded notable approximation algorithms. The classical 1.5-approximation algorithm by Christofides, leveraging matchings, stood as the best-known result for decades. However, recent breakthroughs have pushed these boundaries further.

Title: Nearly-linear stable sets

Abstract: The Gyárfás-Sumner conjecture says that for every forest 𝐻 and complete graph 𝐾, there exists 𝑐 such that every {𝐻,𝐾}-free graph (that is, containing neither of 𝐻,𝐾 as an induced subgraph) has chromatic number at most 𝑐. This is still open, but we have proved that every {𝐻,𝐾}-free graph 𝐺 has chromatic number at most |𝐺|^o(1).

Title: Contracts for Functions Based on Graphs

Abstract: We study contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a contract with several agents, whose actions the principal is unable to observe. The principal is able to see only the outcome of the agents' collective actions; and the outcome is either a success or failure. All agents that decided to exert effort incur costs, and so naturally all agents expect a fraction of the principal's reward as a compensation. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized.

Title: Combinatorial models in enumerative geometry

Abstract: How many circles are tangent to three given circles in the plane?  How many lines lie on a smooth cubic surface? How many lines intersect four given lines in 3-space? These are classical questions in enumerative geometry, a field at least as old as Apollonius of Perga, to whom the question about tangent circles is attributed in the third century BCE.  It is not hard to see that the answers to these questions may depend on the choice of circles, surface, or lines, respectively. It is harder to see that, in each case, there is a "typical" answer. 

Title: On the use of senders in Ramsey Theory

Abstract: In this talk I will introduce and investigate some parameters in Graph Ramsey theory, beyond the traditional Ramsey numbers. A crucial ingredient for their analysis is the existence of gadget graphs, called signal senders, that were initially developed by Burr, Erdős and Lovász in 1976. I will explain their origin, properties, and try to convey their surprising strength. Using probabilistic methods, we will see how to build such gadgets, and how to use them to prove some theorems, previously out of reach without these tools.

Title: Bipartite Perfect Matching is in Quasi-NC, Part II

Abstract: Mulmuley, Vazirani, and Vazirani gave a randomized parallel algorithm for checking whether a perfect matching exists in a graph. In doing so, they came up with the infamous isolation lemma, which found several uses in other areas of computer science. The isolation lemma is inherently randomized, and it has been a long-standing open problem to derandomize the lemma. In this talk, I will go over the breakthrough work of Fenner, Gurjar, and Thierauf where they almost completely derandomize the isolation lemma in the special case when applied to the bipartite perfect matching problem. In doing so, they give a deterministic parallel algorithm for perfect matching that uses a quasi-polynomial number of processors.