Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
Visit our COVID19 information website to learn how Warriors protect Warriors.
Please note: The University of Waterloo is closed for all events until further notice.
Sun  Mon  Tue  Wed  Thu  Fri  Sat 

28

2

3

6







7

9

10

13







14

16

17

20







21

23

24

26

27








28

30

31

1

2

3








Title: Perfect Colorings of the Generalized Petersen Graphs
Speaker: Hamed Karami Affiliation: Iran University of Science and Technology Zoom: Contact Soffia ArnadottirAbstract:
For a graph G and an integer m, a mapping T:V(G) > {1,...,m} is called a perfect mcoloring with matrix A=(a_ij), i,j \in {1,...,m}, if it is surjective, and for all i,j, for every vertex of color i, the number of its neighbors of color j is equal to a_ij. There is another term for this concept in literature as "equitable partition". In this talk, we present some important results about enumerating parameter matrices of all perfect 2colorings and perfect 3colorings of generalized Petersen graphs GP(n,k).
Title: Graphs and combinatorics with a relationship to algebra, geometry and physics
Speaker: Ralph Kaufmann Affiliation: Purdue Zoom: Contact Karen YeatsAbstract:
Several algebraic and geometric structures are most naturally encoded via graphs. These include restrictions, such as trees, and decorations, such as planar graphs, ribbon graphs, bipartite graphs (aka. hypergraphs), directed versions, etc. Particularly nice properties satisfy some kind of hereditary condition. This affords a dual perspective. Either as (nested) subsets and decomposition, or as composition, gluing locally. Both views relate to category theory, algebra, and combinatorics in terms of finite sets, cospans etc. We will give examples of these phenomena and provide a general background.
Title: The ErdosSzekeres theorem
Speaker: Lukas Nabergall Affiliation: University of Waterloo Zoom: Contact Maxwell LevitAbstract:
What lies at the intersection of combinatorial geometry, graph theory, order theory, analysis, and statistics? Why, only one of the most beautiful theorems you may have never heard of. Let me take you on a journey from early 20th century Budapest through to the heights of modern mathematics and show you why this classic result of Erdos and Szekeres is worth adding to your mathematical repertoire. Along the way we'll even see a proof so good it must come from The Book.
Title: The embezzlement of entanglement and its applications
Speaker: Debbie Leung Affliation: University of Waterloo Zoom: Please email Emma WatsonAbstract:
Embezzlement of entanglement is the (impossible) task of producing an entangled state from a product state via a local change of basis, when a suitable *catalytic* entangled state is available.
The possibility to approximate this task was first observed by van Dam and Hayden in 2002. Since then, the phenomenon is found to play crucial roles in many aspects of quantum information theory. In this talk, we will discuss aspects of embezzlement and some applications (such as why quantum correlations do not form a closed set, and why there are nonlocal games that cannot be played optimally with a finite amount of entanglement, and why additive quantities cannot be more than asymptotically continuous).
Title: Lexicographic products, wreath products, and generalisations
Speaker: Joy Morris Affiliation: University of Lethbridge Zoom: Contact Soffia ArnadottirAbstract:
I will present a history and overview of some of the work that has been done on the lexicographic product of graphs, and related generalisations. The focus of my talk will be on the automorphism groups of such graphs, and the relationship to the wreath product of permutation groups.
Title: Equivalences of Wilson loop diagrams
Speaker: Karen Yeats Affiliation: University of Waterloo Zoom: Contact Karen YeatsAbstract:
I will talk about Wilson loop diagrams, explain a bit about what they are, and some of the combinatorial questions that come out of them, with a focus on when they are equivalent. This is joint work with Susama Agarwala and Zee Fryer.
Title: An approximate solution to a 2,079,471point traveling salesman problem
Speaker: Bill Cook Affliation: University of Waterloo Zoom: Please email Emma WatsonAbstract:
Together with Keld Helsguan, we have found a TSP tour through the 3D positions of 2,079,471 stars. We discuss how linear programming allows us to prove the tour is at most a factor of 0.0000074 longer than an optimal solution. The talk will focus on the use of minimum cuts and GF(2) linear systems, to drive the cuttingplane method towards strong LP relaxations.
Title: The chromatic index of strongly regular graphs (joint work with Sebastian M. Cioaba and Krystal Guo)
Speaker: Willem H. Haemers Affiliation: Tilburg University, Tilburg, The Netherlands Zoom: Contact Soffia ArnadottirAbstract:
It follows from Vizing's theorem that the chromatic index (edge chromatic number) of a kregular graph equals k or k+1, and that it equals k+1 if the graph has odd order.
We investigate the chromatic index of strongly regular graphs (SRGs) of even order.
Title: The Poset Conjecture: results, counterexamples, and open problems
Speaker: David Wagner Affiliation: University of Waterloo Zoom: Contact Karen YeatsAbstract:
In 1978, Neggers conjectured that a certain transform of the order polynomial of a partially ordered set (poset) has only real roots.
In the late 1980s, Stanley gave this to me as a thesis project, generalized to labelled posets. For my thesis I proved the conclusion for seriesparallel labelled posets and a bit more. Br\"and\'en, and later Stembridge, found counterexamples to the conjecture in general.
Title: Decompositions of Hypergraphs
Speaker: Felix Joos Affliation: Heidelberg University Zoom: Please email Emma WatsonAbstract:
Several results on approximate decompositions of hypergraphs are presented including decompositions into tight Hamilton cycles under very mild assumptions on the host hypergraphs as well as further results on decompositions of quasirandom hypergraphs into bounded degree hypergraphs.
Title: Centrosymmetric Stochastic Matrices
Speaker: Sarah Plosker Affiliation: Brandon University Zoom: Contact Soffia ArnadottirAbstract:
We consider the convex subset of m by n stochastic matrices that are centrosymmetric: stochastic matrices that are symmetric under rotation by 180 degrees. We consider the extreme points and bases of this set, as well as several other parameters associated to such matrices. We provide examples illustrating the results throughout. This is joint work with Lei Cao (Nova Southeastern University) and Darian McLaren (University of Waterloo).
Title: An Efficient Algorithm for Deciding the Vanishing of Schubert Polynomial Coefficients
Speaker: Colleen Robichaux Affiliation: University of Illinois at UrbanaChampaign Zoom: Contact Karen YeatsAbstract:
Schubert polynomials form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. The vanishing problem for Schubert polynomials asks if a coefficient of a Schubert polynomial is zero. We give a tableau criterion to solve this problem, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the n x n grid. In contrast, we show that computing these coefficients explicitly is #Pcomplete. This is joint work with Anshul Adve and Alexander Yong.
Title: Why are Hoffman's bounds for alpha and chi truly duals of each other?
Speaker: Gabriel Coutinho Affiliation: Universidade Federal de Minas Gerais, Brazil Zoom: Contact Soffia ArnadottirAbstract:
Two of the most well known eigenvalue bounds for graph parameters look suspiciously related. Our goal in this talk is to confirm this suspicion by casting these bounds into a framework of semidefinite optimization that will give us almost for free a duality relation. As one should always expect in this context, we will see a connection to the Lovász theta function of a graph.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, 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 centralized within our Indigenous Initiatives Office.