Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, November 18, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Vera Traub

Title: Approximating Weighted Connectivity Augmentation below Factor 2

Speaker: Vera Traub
Affiliation: Research Institute for Discrete Mathematics, University of Bonn
Location: MC 5501 or contact Melissa Cambridge for Zoom link

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.

Monday, November 21, 2022 6:00 pm - 6:00 pm EST (GMT -05:00)

Algebraic Graph Theory - Daniel Horsley

Title: Exact Zarankiewicz numbers through linear hypergraphs

Speaker: Daniel Horsley
Affiliation: Monash University
Location: Contact Sabrina Lato for Zoom link

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.

Thursday, November 24, 2022 1:00 pm - 1:00 pm EST (GMT -05:00)

Algebraic Combinatorics - Michael Borinsky

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

Speaker: Michael Borinsky
Affiliation: ETH, Zurich
Location: MC 5479 or contact Olya Mandelshtam for Zoom link

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.

Friday, November 25, 2022 12:00 pm - 12:00 pm EST (GMT -05:00)

Combinatorial Optimization Reading Group - Ian DeHaan

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

Speaker: Ian DeHaan
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

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. 

Friday, November 25, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Stefan Weltge

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

Speaker: Stefan Weltge
Affiliation: Technical University of Munich
Location: MC 5501 or contact Eva Lee for Zoom link

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.

Monday, November 28, 2022 11:30 am - 11:30 am EST (GMT -05:00)

Algebraic Graph Theory Seminar - Bogdan Nica

Title: A recursive spectral bound for independence

Speaker: Bogdan Nica
Affiliation: Indiana University-Purdue University Indianapolis
Location: Contact Sabrina Lato for Zoom link

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.

Monday, November 28, 2022 3:00 pm - 3:00 pm EST (GMT -05:00)

Graphs and Matroid Seminar - Hidde Koerts

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

Speaker: Hidde Koerts
Affiliation: University of Waterloo
Location: MC 6029

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.

Thursday, December 1, 2022 1:00 pm - 1:00 pm EST (GMT -05:00)

Algebraic Combinatorics - Sergey Yurkevich

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

Speaker: Sergey Yurkevich
Affiliation: University Paris-Saclay
Location: MC 5479 or contact Olya Mandelshtam for Zoom link

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.

Friday, December 2, 2022 12:00 pm - 12:00 pm EST (GMT -05:00)

Combinatorial Optimization Reading Group - Jacob Skitsko

Title: Boosted Sampling

Speaker: Jacob Skitsko
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

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.

Friday, December 9, 2022 12:00 pm - 12:00 pm EST (GMT -05:00)

Combinatorial Optimization Reading Group - David Aleman

Title: Approximation algorithm for stochastic k-TSP

Speaker: David Aleman
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

Abstract: The input of the deterministic k-TSP problem consists of a metric complete graph with root p in which the nodes are assigned a fixed non-negative reward. The objective is to construct a p-rooted path of minimum length that collects total reward at least k. In this talk we will explore a stochastic variant of this problem in which the rewards assigned to the nodes are independent random variables, and the objective is to derive a policy that minimizes the expected length of a p-rooted path that collects total reward at least k. We will discuss approximation algorithms for this problem proposed in a paper by Ene, Nagarajan and Saket, and a paper by Jiang, Li, Liu and Singla.