Events by month

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.

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.

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,

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.

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.

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.

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.

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.

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

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

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)

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,

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.