Events

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: 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: 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: 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: 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: 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: The spectra of lift and factored lifts of graphs or digraphs

Abstract: In this talk, we first explain the path we took from defining polynomial matrices to a generalization of voltage graphs that we call combined voltage graphs. Moreover, we give a general definition of a matrix associated with a combined voltage graph, which allows us to provide a new method for computing the eigenvalues and eigenspaces of such graphs. 

Title: NC algorithm to find perfect matching in planar graphs

Abstract: Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution.