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 4, 2022 12:00 pm - 12:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - David Aleman

Title: Approximation Algorithms for Stochastic Knapsack 

Speaker: David Aleman
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Ne

Abstract: The classical Knapsack problem takes as input a set of items with some fixed nonnegative values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is at most a given limit. In this talk we review a paper by Gupta, Krishnaswamy, Molinaro and Ravi, in which the following stochastic variation of this problem is considered: the value and weight of each item are correlated random variables with known, arbitrary distributions.

Friday, November 4, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Jim Geelen

Title: Sylvester, Gallai, and their complex relatives

Speaker: Jim Geelen
Affiliation: University of Waterloo
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: Given any finite set of points in the real plane, not all collinear, there is a line in the plane that contains exactly two of them. This pretty result was conjectured by Sylvester in 1893 and proved by Gallai in 1944. We will present an extension of the result to higher dimensional complex spaces and discuss some related conjectures. This is joint work with Matthew Kroeker.

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

Algebraic Graph Theory - Soffía Árnadóttir

Title: Cayley graphs, association schemes and state transfer

Speaker: Soffía Árnadóttir
Affiliation: Technical University of Denmark
Location: contact Sabrina Lato for Zoom link

Abstract: The aim of this talk is to give some examples of how association schemes can be used as a tool to study certain properties of Cayley graphs. In particular, they contribute to our long-term goal of characterizing perfect state transfer in Cayley graphs. The talk is based on the following paper https://arxiv.org/abs/2204.09802.

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

Algebraic Combinatorics Seminar - Theo Douvropoulos

Title: Recursions and Proofs in Coxeter-Catalan combinatorics

Speaker: Theo Douvropoulos
Affiliations: U Mass Amherst
Location: MC 5479 or contact Olya Mandelshtam for Zoom link

Abstract:  The collection of parking functions under a natural Sn-action (which has Catalan-many orbits) has been a central object in Algebraic Combinatorics since the work of Haiman more than 30 years ago. One of the lines of research spawned around it was towards defining and studying analogous objects for real and complex reflection groups W; the main candidates are known as the W-non-nesting and W-non-crossing parking functions.

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

Combinatorial Optimization Reading Group - Sharat Ibrahimpur

Title: Stochastic Minimum Norm Combinatorial Optimization

Speaker: Sharat Ibrahimpur
Affiliation:  
Location: MC 6029 or contact Rian Neogi for Zoom link

Abstract:  In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a framework for designing approximation algorithms for stochastic minimum-norm optimization and apply it to give approximation algorithms for stochastic minimum-norm versions of load balancing and spanning tree problems.

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

Tutte Colloquium - Linda Cook

Title: Forbidding some induced cycles in a graph

Speaker: Linda Cook
Affiliation: Institute for Basic Science, South Korea
Location: MC 5501 or contact Melissa Cambridge for Zoom link

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.

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

Algebraic Graph Theory Seminar - Paul Horn

Title: Graphs, curvature, and local discrepancy

Speaker: Paul Horn
Affiliation: University of Denver
Location: contact Sabrina Lato for Zoom link

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. 

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

Graphs and Matroids Seminar - Jeremy Chizewer

Title: The Hat Guessing Number of Graphs

Speaker: Jeremy Chizewer
Affiliation: University of Waterloo
Location: MC 6029

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.

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

Algebraic Graph Theory Seminar - Josip Smolcic

Title: Algorithms for Analytic Combinatorics in Several Variables

Speaker: Josip Smolcic
Affiliation: University of Waterloo
Location: MC 5479

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.

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

Combinatorial Optimization Reading Group - Madison Van Dyk

Title: Approximation algorithms for stochastic orienteering  

Speaker: Madison Van Dyk
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

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.