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 

30

31

1

2

3

5









6

8

9

10

12








13

15

16

19







20

22

23

26







27

29

30

1

2

3








Title: Recent proximity results in integer linear programming
Speaker: Joseph Paat Affiliation: UBC Sauder School of Business Zoom: Please email Emma Watson.Abstract:
We consider the proximity question in integer linear programming (ILP)  Given a vector in a polyhedron, how close is the nearest integer vector? Proximity has been studied for decades with two influential results due to Cook et al. in 1986 and Eisenbrand and Weismantel in 2018. We derive new upper bounds on proximity using sparse integer solutions and mixed integer relaxations of the integer hull. When compared to previous bounds, these new bounds depend less on the dimensions of the constraint matrix and more on the data in the matrix.
Title: Projective Planes, Finite and Infinite
Speaker: Eric Moorhouse Affiliation: University of Wyoming Zoom: Contact Soffia ArnadottirAbstract:
A projective plane is a pointline incidence structure in which every pair of distinct points has a unique joining line, and every pair of distinct lines meets in a unique point. Equivalently (as described by its incidence graph), it is a bipartite graph of diameter 3 and girth 6.
Title: Further progress towards Hadwiger's conjecture
Speaker: Luke Postle Affiliation: University of Waterloo Zoom: Please email Emma Watson.Abstract:
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t1)$colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$colorable.
Title: Extensions of the ErdősKoRado theorem to 2intersecting perfect matchings and 2intersecting permutations
Speakers: Andriaherimanana Sarobidy Razafimahatratra & Mahsa Nasrollahi Shirazi Affiliation: University of Regina Zoom: Contact Soffia ArnadottirAbstract:
The ErdősKoRado (EKR) theorem is a classical result in extremal combinatorics. It states that if n and k are such that $n\geq 2k$, then any intersecting family F of ksubsets of [n] = {1,2,...,n} has size at most $\binom{n1}{k1}$. Moreover, if n>2k, then equality holds if and only if F is a canonical intersecting family; that is, $\bigcap_{A\in F}A = \{i\}$, for some i in [n].
Title: Foundations of Matroids without Large Uniform Minors, Part 2
Speaker: Oliver Lorscheid Affiliation: Instituto Nacional de Matemática Pura e Aplicada Zoom: Contact Rose McCartyAbstract:
In this talk, we take a look under the hood of last week’s talk by Matt Baker: we inspect the foundation of a matroid.
The first desired properties follow readily from its definition: the foundation represents the rescaling classes of the matroid and shows a functorial behaviour with respect to minors and dualization.
The profound impact of early discovery, experimentation, and disruption through research and invention
Researchers today build on the knowledge and discoveries made by those who have come before them. How can today’s researchers light the early pathways and curiosities for the research breakthroughs of the future? How can we demonstrate the impact and potential of the yettobe known? And, what if any, role does academia, industry, the Faculty of Mathematics, and Canada play in increasing the discovery journey to these new frontiers?
Title: Edge DeletionContraction in the Chromatic and Tutte Symmetric Functions
Speaker: Logan Crew Affiliation: University of Waterloo Zoom: Contact Karen YeatsAbstract:
We consider symmetric function analogues of the chromatic and Tutte polynomials on graphs whose vertices have positive integer weights. We show that in this setting these functions admit edge deletioncontraction relations akin to those of the corresponding polynomials, and we use these relations to give enumerative and/or inductive proofs of properties of these functions.
Title: Hard Combinatorial Problems, Doubly Nonnegative Relaxations, Facial
and Symmetry Reduction, and Alternating Direction Method of Multipliers
Abstract:
Semidefinite programming, SDP, relaxations have proven to be extremely successful both in theory and practice for many hard combinatorial problems. This is particularly true for the MaxCut problem, where problems of dimension in the thousands have been solved to optimality. In contrast, the quadratic assignment problem, QAP, is an NPhard problem where dimensions bigger than $30$ are still considered hard. SDP and in particular, the doubly nonnegative, DNN, relaxation have been successful in providing strong upper and lower bounds, and even solving many instances to optimality.
Title: Leonard pairs, spin models, and distanceregular graphs
Speaker: Paul Terwilliger Affiliation: University of Wisconsin Zoom: Contact Soffia ArnadottirAbstract:
A Leonard pair is an ordered pair of diagonalizable linear maps on a finitedimensional vector space, that each act on an eigenbasis for the other one in an irreducible tridiagonal fashion. In this talk we consider a type of Leonard pair, said to have spin.
Title: Sign variations and descents
Speaker: Aram Dermenjian Affiliation: York University Zoom: Contact Karen YeatsAbstract:
In this talk we consider a poset structure on projective sign vectors. We show that the order complex of this poset is partitionable and give an interpretation of the hvector using type B descents of the type D Coxeter group.
Title: Rota's Basis Conjecture holds asymptotically
Speaker: Alexey Pokrovskiy Affiliation: Birkbeck, University of London Zoom: Please email Emma WatsonAbstract:
Rota's Basis Conjecture is a well known problem, that states that for any collection of n bases in a rank n matroid, it is possible to decompose all the elements into n disjoint rainbow bases. Here an asymptotic version of this is will be discussed  that it is possible to find n − o(n) disjoint rainbow independent sets of size n − o(n).
Title: Strongly cospectral vertices, Cayley graphs and other things
Speaker: Soffia Arnadottir Affiliation: University of Waterloo Zoom: Contact Soffia ArnadottirAbstract:
In this talk we will look at a connection between the number of pairwise strongly cospectral vertices in a translation graph (a Cayley graph of an abelian group) and the multiplicities of its eigenvalues. We will use this connection to give an upper bound on the number of pairwise strongly cospectral vertices in cubelike graphs.
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.