Events

Hardness of computing clique number and chromatic number for cayley graphs

Abstract:

Computing the clique number and chromatic number of a general graph are well-known to be NP-Hard problems. Codenotti et al. (Bruno Codenotti, Ivan Gerace, and Sebastiano Vigna.

Macdonald Symmetric Functions and Parking Functions

Abstract:

A parking function can be thought of as a Dyck path of length n where the vertical edges are labeled with the integers 1 through n, increasing in the columns. 

Students with offers of admissions to MMath or PhD programs in the Faculty of Mathematics at the University of Waterloo will visit campus on February 27 for a full-day open house. The visiting students will be taken for a tour of campus, and will be given an overview of the unique and rich research environment in the Faculty of Mathematics and its five academic units -- Applied Mathematics, Combinatorics and Optimization (C and O), Computer Science, Pure Mathematics, and Statistics and Actuarial Science.

The structure of triangle-free graphs and geometries

Abstract:

Brandt and Thomass\'{e} proved that a triangle-free graph $G$ of minimum degree greater than $\frac{1}{3}|V(G)|$ has chromatic number at most $4$.

Simple Submodular Function Minimization

Abstract:

In combinatorics, submodular functions abound. Some common examples include the cut capacity function of a graph and the rank function of a matroid.

The algebra of flows in graphs

Abstract:

We sketch the construction of a finitely generated graded abelian group $K^\cdot(X)$ associated to a graph $X$ which encodes Kirchhoff's Current Law on $X$ and all its contractions, in such a way that $\hom(K^1(X),R)$ is the familiar (real) cycle-space of $X$.

Cores of cubelike graphs

Abstract:

A graph is said to be cubelike if it is a Cayley graph for some power of the field of order two. The core of a graph is its smallest subgraph to which it admits a homomorphism. In this talk we consider the following open question: Is the core of a cubelike graph cubelike?

Rigidity, Unique Vector Colorings, and Cores

Abstract:

A vector $t$-coloring of a graph is an assignment of unit vectors to the vertices of the graph such that the inner product of vectors assigned to adjacent vertices is less than or equal to $-1/(t-1)$.

Faculty, graduate students, postdoctoral fellows and visitors are invited to attend the C&O department's annual potluck dinner. Family members are also welcome! The dinner will be held in the fishbowl (William G. Davis Computer Research Centre (DC) 1301), and will begin at 5:00 p.m. The department will provide a main course and beverages; please bring a salad or a dessert.

Please let Marie know by March 3 if you will be attending, the number of guests you will be bringing, and whether you will be bringing a salad or dessert.

Cybersecurity in a quantum world - will we be ready?

Abstract:

Emerging quantum technologies will change the way that our online information is stored and secured. To be cyber-safe we must be quantum-safe. It's possible, but we need to start planning now if we want to be ready in time.