Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
DataFest 2022 registration is now OPEN!
Register online now!
All members of your team must register.
The American Statistical Association (ASA) DataFest is a celebration of data in which teams of undergraduates work around the clock to find and share meaning in a large, rich, and complex data set.
Title: On the eigenvalues of the perfect matching derangement graph
Speaker: | Mahsa N. Shirazi |
Affiliation: | University of Regina |
Zoom: | Contact Sabrina Lato for link |
Abstract:
The perfect matching derangement graph $M_{2n}$ is defined to be the graph whose vertices are all the perfect matchings of the complete graph $K_{2n}$, and two vertices are adjacent if they contain no common edges. The graph $M_{2n}$ is part of a larger study on the analogs of the Erdős-Ko-Rado theorem, and recently there have been interesting works on $M_{2n}$ and its eigenvalues.
Title: Speeding up Multi-Scalar Multiplication over Fixed Points towards Efficient zkSNARKs
Speaker: | Guiwen Luo |
Affiliation: | University of Waterloo |
Attend: | Contact Jesse Elliott |
Abstract:
The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in pairing-based trusted setup zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs), thus fast algorithms of MSM over fixed points are desirable for practical applications.
Join us for a panel discussion focused on understanding and promoting equity, diversity, and inclusion (EDI) in academic settings. All members of our academic communities should strive to create equitable, diverse, and inclusive environments.
Title: The one-sided cycle shuffles in the symmetric group algebra
Speaker: | Darij Grinberg |
Affiliation: | Drexel University |
Zoom: | Contact Logan Crew or Olya Mandelshtam |
Abstract:
Elements in the group algebra of a symmetric group S_n are known to have an interpretation in terms of card shuffling. I will discuss a new family of such elements, recently constructed by Nadia Lafrenière: Given a positive integer n, we define n elements t_1, t_2, ..., t_n in
Title: Generating Short Monotone Paths in 0/1 LPs: From Circuits to Simplex
Speaker: | Sean Kafer |
Affiliation: | University of Waterloo |
Zoom: | 945 0789 9910 (passcode: kafer) |
Abstract:
Even after decades of study, it is unknown whether there exists a pivot rule for the Simplex method that always solves an LP with only a polynomial number of pivots. This remains unknown even in the special case of 0/1 LPs - i.e., LPs defined over 0/1 polytopes - a case that includes many extensively studied problems in combinatorial optimization.
Title: Lattice path matroids, lattice path polymatroids, and excluded minors
Speaker: | Carolyn Chun |
Affiliation: | US Naval Academy |
Zoom: | http://matroidunion.org/?page_id=2477 or contact Shayla Redlin |
Abstract:
We define lattice path matroids, polymatroids, Boolean polymatroids, and lattice path polymatroids, which are a subclass of Boolean polymatroids.
Title: Deletion-contraction for a unified Laplacian and applications
Speaker: | Victor Wang |
Affiliation: | University of British Columbia |
Zoom: | Contact Sabrina Lato |
Abstract:
We define a graph Laplacian with vertex weights in addition to the more classical edge weights, which unifies the combinatorial Laplacian and the normalised Laplacian.
Title: Modular relations between chromatic symmetric functions
Speaker: | Farid Aliniaeifard |
Affiliation: | University of British Columbia |
Zoom: | Contact Logan Crew or Olya Mandelshtam |
Abstract:
In 1995, Stanley introduced the chromatic symmetric functions. The study of chromatic symmetric functions of graphs inspired two main research directions.
Title: A local version of Hadwiger’s Conjecture
Speaker: | Lise Turner |
Affiliation: | University of Waterloo |
Zoom: | http://matroidunion.org/?page_id=2477 or contact Shayla Redlin |
Abstract:
In 1943, Hadwiger famously conjectured that graphs with no $K_t$ minors are $t-1$ colourable. There has also been significant interest in several variants of the problem, such as list colouring or only forbidding certain classes of minors.
Title: Yet Another Proof of the Erdős-Ko-Rado Theorem
Speaker: | Nathan Lindzey |
Affiliation: | University of Colorado, Boulder |
Zoom: | Contact Sabrina Lato |
Abstract:
We give a short new algebraic proof of the Erdős-Ko-Rado theorem, that for k < n/2, the largest families of k-sets of an n-element set such that any two of its members intersect are precisely those families composed of all k-sets that contain some fixed element.
Title: SAT Solving with Computer Algebra for Combinatorics
Speaker: | Curtis Bright |
Affiliation: | University of Windsor and Carleton University |
Location: | MC 5501 or please contact Emma Watson for Zoom link |
Abstract:
This talk will describe a method of solving combinatorial problems by coupling Boolean satisfiability (SAT) solvers with computer algebra systems (CASs), thereby combining the search and learning power of SAT solvers with the expressiveness and mathematical sophistication of CASs.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.