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, October 20, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Sepehr Assadi

Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams 

Speaker: Sepehr Assadi
Affiliation: University of Waterloo
Location: MC 5501

Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.

Thursday, October 26, 2023 2:00 pm - 2:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics Seminar - David Wagner

Title: Higher-order correlation inequalities for random spanning trees

Speaker: David Wagner
Affiliation: University of Waterloo
Location: MC 6029

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.

Abstract: The connection between enumerating spanning trees of a graph and the theory of (linear) electrical networks goes all the way back to Kirchhoff's 1847 paper. It is physically sensible that if one increases the conductance of one wire in an electrical network, then the overall conductance of the network can not decrease. This corresponds to the less obvious fact that any two distinct edges are non-positively correlated, when one chooses a random spanning tree. Covariance is the 2-point "Ursell function'', and expectation is the 1-point Ursell function. For any subset of edges there is an associated Ursell function, and these are related to occupation probabilities by Möbius inversion. I will discuss some situations in which the signs of these Ursell functions can be predicted, yielding higher-order correlation inequalities for random spanning trees.

Thursday, October 26, 2023 3:00 pm - 3:00 pm EDT (GMT -04:00)

Graphs and Matroids Seminar - Dao Chen Yuan

Title: Chromatic Number of Random Signed Graphs

Speaker: Dao Chen Yuan
Affiliation: University of Waterloo
Location: MC 5417

Abstract: A signed graph is a graph where edges are labelled {+1,-1}. A signed colouring in 2k colours maps the vertices of a signed graph to {-k,...,-1,1,...,k}, such that neighbours joined by a positive edge do not share the same colour, and those joined by a negative edge do not share opposite colours. It is a classical result that the chromatic number of a G(n,p) Erdos-Renyi random graph is asymptotically almost surely n/(2log_b(n)), where p is constant and b=1/(1-p). We extend the method used there to prove that the chromatic number of a G(n,p,q) random signed graph, where q is the probability that an edge is labelled -1, is also a.a.s. n/(2log_b(n)), if p is constant and q=o(1).

Monday, October 30, 2023 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory - Shaun Fallat

Title: Graphs that Admit Orthogonal Matrices

Speaker: Shaun Fallat
Affiliation: University of Regina
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Given a simple graph $G=(\{1,\ldots, n},E), we consider the class $S(G)$ of real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}\neq 0$ iff $ij \in E$. Under the umbrella of the inverse eigenvalue problem for graphs (IEPG), $q(G)$ - known as the minimum number of distinct eigenvalues of $G$ - has emerged as one of the most well-studied parameters of the IEPG. Naturally, characterizing graphs $G$ for which $q(G) \leq, =, \geq k$ is an important step for studying the IEPG.

Thursday, November 2, 2023 2:00 pm - 2:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics Seminar - Jerónimo Valencia-Porras

Title: Snake decompositions of lattice path matroids

Speaker: Jerónimo Valencia-Porras
Affiliation: University of Waterloo
Location: MC 6029

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.

Abstract: We study Ehrhart theory of lattice path matroid polytopes motivated by a conjecture by De Loera, Haws and Köppe. More specifically, we aim to understand the h*-vector of this family of matroid polytopes. To do so, we subdivide them into smaller matroid polytopes such that each piece is a snake, which are matroids such that their matroid polytope coincides with the order polytope of a fence poset.

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

Tutte Colloquium - Walaa Moursi

Title: The Chambolle-Pock algorithm revisited: splitting operator and its range with applications

Speaker: Walaa Moursi
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.

Monday, November 6, 2023 11:30 am - 11:30 am EST (GMT -05:00)

Algebraic Graph Theory - Jane Breen

Title: Kemeny’s constant and random walks on graphs

Speaker: Jane Breen
Affiliation: Ontario Tech University
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Kemeny's constant is an interesting and useful quantifier of how well-connected the states of a Markov chain are. This comes to the forefront when the Markov chain in question is a random walk on a graph, in which case Kemeny's constant is interpreted as a measure of how `well-connected' the graph is. Though it was first introduced in the 1960s, interest in this concept has recently exploded. This talk will provide an introduction to Markov chains, an overview of the history of Kemeny’s constant, discussion of some applications, and a survey of recent results, with an emphasis on those that are extensions or generalizations of simple random walks on graphs, to complement Sooyeong’s talk from two weeks ago.

Thursday, November 9, 2023 2:00 pm - 2:00 pm EST (GMT -05:00)

Algebraic and Enumerative Combinatorics Seminar - Spencer Daugherty

Title: Extended Schur Functions and Bases Related by Involutions

Speaker: Spencer Daugherty
Affiliation: North Carolina State University
Location: MC 6029

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.

Abstract: The extended Schur basis and the shin basis generalize the Schur functions to the dual algebras of the quasisymmetric functions and the noncommutative symmetric functions. We define a creation operator and a Jacobi-Trudi rule for certain shin functions and show that a similar matrix determinant expression does not exist for every shin function.

Thursday, November 9, 2023 3:00 pm - 3:00 pm EST (GMT -05:00)

Graphs and Matroids Seminar - Josephine Reynes

Title: The Tutte Polynomial, Bipartite Representations of Graphs, and Grid Walking 

Speaker: Josephine Reynes
Affiliation: University of Waterloo
Location: MC 5417

Abstract: The Tutte Polynomial has many equivalent definitions. It can be defined by a deletion-contraction relation with the terms determined by the sequence of contractions, deletions, loops, and isthmi. This definition is independent of edge order. Another definition relies on a fixed edge ordering and examines the edge activities over maximal spanning forests. There is a direct relationship between edge activity and deletion/contraction for a given edge ordering. Furthermore, the monomials of the Tutte polynomial can be interpreted as grid walks. This allows for an approach to the Tutte polynomial on hypergraphs by examining the grid walks of the bipartite representation of the graph.

Friday, November 10, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Distinguished Tutte Lecture - David B. Shmoys

Title: Algorithmic Tools for Congressional Districting: Fairness via Analytics

Speaker: David B. Shmoys
Affiliation: Cornell University
Location: MC 5501

Abstract: The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.