Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Thursday, February 28, 2019 — 3:30 PM EST
Title: Difference-of-SOS and Difference-of-Convex-SOS Decomposition Techniques for Polynomials
| Speaker: | Yi-Shuai Niu |
| Affiliation: |
SJTU-Paristech & Maths department Shanghai Jiao Tong University |
| Room: | MC 5501 |
Abstract:
We are interested in polynomial decomposition techniques for reformulating any multivariate polynomial into difference-of-sums-of-squares (DSOS) and difference-of-convex-sums-of-squares (DCSOS) polynomials.
Wednesday, February 27, 2019 — 3:30 PM EST
Title: Cyclic flat approach to matroid base polytopes
| Speaker: | Ahmed Ashraf |
| Affiliation: | Western University |
| Room: | MC 5501 |
Abstract: Ardila, Benedetti and Doker realised matroid polytopes as generalized permutohedra, and using the work of Postnikov,
Tuesday, February 26, 2019 — 2:00 PM EST
Title: Bounding Dedekind numbers with entropy
| Speaker: | John Schanck |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: The Dedekind numbers (sequence A000372 in the OEIS)
Tuesday, February 19, 2019 — 2:00 PM EST
Title: Applications of the entropy method: Counting proper colorings of a regular graph
| Speaker: | Jane Gao |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: Following Section 6 of Galvin's notes on Entropy and Counting, we will explore Galvin and Tetali’s tight upper bound
Friday, February 15, 2019 — 1:00 PM EST
Title: Coloring 3-colorable graphs with o(n^1/5) colors
| Speaker: | Sharat Ibrahimpur |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: This is the second part of the seminar on recent results obtained by Kawarabayashi and Thorup
Thursday, February 14, 2019 — 1:30 PM EST
Title: Quantum Walks, State Transfer, and Entanglement
| Speaker: | Christopher van Bommel |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: Quantum walks are the quantum analogues of classical random walks and can be used to model quantum computations.
Wednesday, February 13, 2019 — 3:30 PM EST
Title: Circle graphs are quadratically x-bounded
| Speaker: | James Davies |
| Affiliation: | University of Waterloo |
| Room: | **New Room** MC 5501 |
Abstract: A circle graph $G$ is an intersection graph of a set of chords on a circle.
Friday, February 8, 2019 — 3:30 PM EST
Title: The rank of random matrices over finite fields
| Speaker: | Jane Gao |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We determine the rank of a random matrix over a finite field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes.
Friday, February 8, 2019 — 1:00 PM EST
Title:‘Coloring 3-colorable graphs with o(n^1⁄5) colors’ by Kawarabayashi and Thorup
| Speaker: | Tom Kelly |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: Much attention has been devoted to nding polynomial time algorithms for coloring three-
colorable graphs with the fewest possible colors.
Thursday, February 7, 2019 — 1:30 PM EST
Title: Permutation Problems, Chessboards, and Rook Equivalence
| Speaker: | Caelan Wang |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: We discuss the motivation and development of the theory around rook polynomials.
Tuesday, February 5, 2019 — 2:00 PM EST
Title: Applications of the entropy method: Brégman's theorem
| Speaker: | Jorn van der Pol |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: Following Section 5 of Galvin's notes on Entropy and Counting,
Friday, February 1, 2019 — 3:30 PM EST
Title: Eigenvalue bounds to the (co)clique and chromatic numbers
| Speaker: | Gabriel Coutinho |
| Affiliation: | Federal University of Minas Gerais, Brazil |
| Room: | MC 5501 |
Abstract:
This is perhaps one of the oldest topics of interest in spectral graph theory, dating back to the works of Hoffman, Haemers, Delsarte and others, in the 70s.
Friday, February 1, 2019 — 1:00 PM EST
Title: 2-approximation of chromatic number on graph classes excluding a minor
| Speaker: | Rose McCarty |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: In this talk we will see a 2-approximation of the chromatic number of graphs excluding a fixed minor.