#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Monday, March 29, 2021 11:30 AM EDT

**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 Arnadottir |

**Abstract:**

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.

Thursday, March 25, 2021 1:00 PM EDT

**Title:** An Efficient Algorithm for Deciding the Vanishing of Schubert Polynomial Coefficients

Speaker: | Colleen Robichaux |

Affiliation: | University of Illinois at Urbana-Champaign |

Zoom: | Contact Karen Yeats |

**Abstract:**

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 #P-complete. This is joint work with Anshul Adve and Alexander Yong.

Monday, March 22, 2021 11:30 AM EDT

**Title:** Centrosymmetric Stochastic Matrices

Speaker: | Sarah Plosker |

Affiliation: | Brandon University |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

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).

Friday, March 19, 2021 3:30 PM EDT

**Title: **Decompositions of Hypergraphs

Speaker: | Felix Joos |

Affliation: | Heidelberg University |

Zoom: | Please email Emma Watson |

**Abstract:**

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.

Thursday, March 18, 2021 1:00 PM EDT

**Title:** The Poset Conjecture: results, counterexamples, and open problems

Speaker: | David Wagner |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

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 series-parallel labelled posets and a bit more. Br\"and\'en, and later Stembridge, found counterexamples to the conjecture in general.

Monday, March 15, 2021 11:30 AM EDT

**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 Arnadottir |

**Abstract:**

It follows from Vizing's theorem that the chromatic index (edge chromatic number) of a k-regular 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.

Friday, March 12, 2021 3:30 PM EST

**Title: **An approximate solution to a 2,079,471-point traveling salesman problem

Speaker: | Bill Cook |

Affliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

**Abstract:**

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 cutting-plane method towards strong LP relaxations.

Thursday, March 11, 2021 1:00 PM EST

**Title:** Equivalences of Wilson loop diagrams

Speaker: | Karen Yeats |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

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.

Monday, March 8, 2021 11:30 AM EST

**Title:** Lexicographic products, wreath products, and generalisations

Speaker: | Joy Morris |

Affiliation: | University of Lethbridge |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

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.

Friday, March 5, 2021 3:30 PM EST

**Title: **The embezzlement of entanglement and its applications

Speaker: | Debbie Leung |

Affliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

**Abstract:**

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).

Thursday, March 4, 2021 4:00 PM EST

**Title:** The Erdos-Szekeres theorem

Speaker: | Lukas Nabergall |

Affiliation: | University of Waterloo |

Zoom: | Contact Maxwell Levit |

**Abstract:**

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.

Thursday, March 4, 2021 1:00 PM EST

**Title:** Graphs and combinatorics with a relationship to algebra, geometry and physics

Speaker: | Ralph Kaufmann |

Affiliation: | Purdue |

Zoom: | Contact Karen Yeats |

**Abstract:**

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, bi-partite 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.

Monday, March 1, 2021 11:30 AM EST

**Title:** Perfect Colorings of the Generalized Petersen Graphs

Speaker: | Hamed Karami |

Affiliation: | Iran University of Science and Technology |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

For a graph G and an integer m, a mapping T:V(G) -> {1,...,m} is called a perfect m-coloring 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 2-colorings and perfect 3-colorings of generalized Petersen graphs GP(n,k).

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

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.