Events

Title: Forbidding some induced cycles in a graph

Abstract:  We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain lengths in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković provided a structural description of the class of even-hole-free graphs.

Title: Graphs, curvature, and local discrepancy

Abstract: Spectral graph theory, the use of eigenvalues to study graphs, gives an important window into many properties of graphs.  One of the reasons for this is that the eigenvalues can be used to certify the `pseudo-randomness' of the edge set of a graph.  In recent years, several notions of discrete curvature have been introduced that gives a 'local' way (depending on the neighborhood structure of vertices) to study some of the same properties that eigenvalues can capture. 

Title: The Hat Guessing Number of Graphs

Abstract:  The hat guessing number HG(G) of a graph G on n vertices is defined in terms of the following game: n players are placed on the n vertices of G, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The hat guessing number HG(G) is the largest integer q such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of q possible colors.

Title: Algorithms for Analytic Combinatorics in Several Variables

Abstract: In this presentation we will see how to apply the theory of complex analysis to study multivariate generating series by looking at several examples. Specifically, given a rational bivariate generating function G(x, y)/H(x, y) with coefficients f_{i, j} the objective is algorithmically determine asymptotic formulas to approximate f_{rn, sn} as n goes to infinity, for fixed positive integers r and s.

Title: Approximation algorithms for stochastic orienteering  

Abstract: This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed.

Title: Approximating Weighted Connectivity Augmentation below Factor 2

Abstract:  The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques.

Title: Exact Zarankiewicz numbers through linear hypergraphs

Abstract: The \emph{Zarankiewicz number} $Z_{2,2}(m,n)$ is usually defined as the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no $K_{2,2}$ subgraph. An equivalent definition is that $Z_{2,2}(m,n)$ is the greatest total degree of a linear hypergraph with $m$ vertices and $n$ edges. A hypergraph is \emph{linear} if each pair of vertices appear together in at most one edge. The equivalence of the two definitions can be seen by considering the bipartite incidence graph of the linear hypergraph.

Title: Asymptotics of the Euler characteristic of Kontsevich's commutative graph complex

Abstract: I will present results on the asymptotic growth rate of the Euler characteristic of Kontsevich's commutative graph complex. By a work of Chan-Galatius-Payne, these results imply the same asymptotic growth rate for the top-weight Euler characteristic of M_g, the moduli 
space of curves, and establish the existence of large amounts of unexplained cohomology in this space. This asymptotic growth rate 
follows from new generating functions for the edge-alternating sum of graphs without odd automorphisms. I will give an overview on this 
interaction between topology and combinatorics and illustrate the combinatorial and analytical tools that were needed to obtain these 
generating functions.

Title: Greedy algorithm for stochastic matching is a 2-approximatio

Abstract: We will discuss the greedy algorithm for the stochastic matching problem. In this problem, we are given an undirected graph where each edge is assigned a probability p_e in [0, 1] and each vertex is assigned a patience t_v in Z+. We begin each step by probing an edge e which is not adjacent to any edges in our matching. The probe will succeed with probability p_e, and if it does, we add e to our matching. Otherwise, we may not probe e again. We also may not probe edges adjacent to a vertex v more than t_v times. The goal is to maximize the number of edges we add to our matching. 

Title: Integer programs with bounded subdeterminants and two nonzeros per row

Abstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomial-time algorithm for such integer programs with the further requirement that every constraint contains at most two variables. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k = 0 (bipartite graphs) and for k = 1.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.