Seminar

Titile: Global geometric reductions for some bottleneck questions in hardness of approximation

Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.

Title: Boosted Sampling

Abstract: We will discuss the boosted sampling technique introduced by Gupta et al. which approximates the stochastic version of problems by using nice approximation algorithms for the deterministic version of the problem. We will focus on rooted stochastic Steiner trees as an example, though other problems are covered by this approach (such as vertex cover and facility location). The problem is given to us in two stages: in the first stage we may choose some elements at a cheaper cost, and in the second stage our actual requirements are revealed to us, and we can buy remaining needed elements at a more expensive cost (where costs get scaled by some factor in the second stage). We will see that if our problem is sub-additive, and we have an alpha-approximation algorithm for the deterministic version of our problem with a beta-strict cost-sharing function then we can get an (alpha + beta)-approximation for the stochastic version of our problem. We also discuss related problems, for example the (not sub-additive!) unrooted stochastic Steiner tree problem.

Title: Algebraicity of solutions of functional equations with one catalytic variable

Abstract: Abstract: Numerous combinatorial enumeration problems reduce to the study of functional equations which can be solved by a uniform method introduced by Bousquet-Mélou and Jehanne in 2006. In my talk, I will first briefly explain this result and its proof. Then I will present a new generalization of it to the case of systems of functional equations with one catalytic variable. The method is constructive and yields an algorithm for computing the minimal polynomials of interest.

Title: A recursive spectral bound for independence

Abstract: We discuss an upper bound for the independence number of a graph, in the spirit of the well-known Hoffman bound. Our bound involves the largest Laplacian eigenvalue of the graph; more surprisingly, it also involves the independence number of a certain induced graph. We illustrate the bound on several examples.

Title: k-Connectedness and k-Factors in the Semi-Random Graph Process

Abstract: The semi-random graph process is a single player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently chooses a second vertex v deterministically according to some strategy, and adds edge uv to the graph. The objective for the player is then to ensure that the graph fulfils some specified property as fast as possible.

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: 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: 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: 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.