Combinatorics Seminar

Organizers: David Gunderson and Karen Gunderson
Time: Fridays 3:30pm
Room: 415 Machray Hall 418 Machray Hall

Topics including graphs and hypergraphs, algebraic graph theory, finite geometries, random processes, extremal or Ramsey theory, applications of combinatorics, combinatorial geometry, partial orders, design theory, combinatorial matrix theory, additive combinatorics.

Talks can be surveys, works in progress, introductions to an area, or recent results. All are welcome to attend and to volunteer talks. Talks should be aimed at a wide audience of combinatorialists and should be understandable to graduate students.

Extremal C15-free graph

Subscription to the calendar is available via:

Schedules for past seminars are available here.

Winter 2019 Schedule

Date Speaker Title
15 Feb 2019
22 Feb 2019
1 Mar 2019 Rob Craigen Orthogonal matrices with zero diagonal
15 Mar 2019 Karen Gunderson Minimum percolating sets
22 Mar 2019
28 Mar 2019 Andriy Prymak On illumination of the boundary of a convex body in E^n, n=4,5,6.
5 Apr 2019 Xiaohong Zhang Quantum state transfer on graphs

Graph with every pair of vertices having
exactly 2 common neighbours


1 March 2019, 3:30 pm, 418 Machray Hall

Speaker: Rob Craigen
Title: Orthogonal matrices with zero diagonal

Abstract: A couple of years ago Robert Bailey (UMN) asked me whether I knew a way to determine for which $n$ there is a real $n\times n$ orthogonal matrix with zero diagonal, but nonzero in all other positions. At the time I thought the problem to be too simple to take seriously, but found out it was going to take more than a few moment’s reflection. The question falls properly in a class of problems concerning the degree to which specified properties of a matrix are constrained by rather coarse assumptions about the "shape" of the matrix---usually things like the pattern of zeros or the pattern of signs of the (real) entries of the matrix. At first glance this particular case seems straightforward. The interest in this case comes from a question in graph theory in which one examines the minimum number of distinct eigenvalues possible among matrices associated in a certain way with graphs, in which progress has been slow and in particular it seemed difficult to close the question for the graph obtained by deleting a perfect matching from the complete bipartite graph $K_{n,n}$. I discuss our solution to the matrix question and some variants.

15 March 2019, 3:30 pm, 418 Machray Hall

Speaker: Karen Gunderson
Title: Minimum percolating sets

Abstract: The r-neighbour bootstrap process is an update rule for the states of vertices in a graph where uninfected vertices with at least r infected neighbours become infected and a set of initially infected vertices is said to percolate if eventually all vertices are infected. While the focus is often on whether a randomly chosen set percolates, one can ask for the minimum size of a percolating set for a graph in such a process and which graph properties guarantee the existence of small percolating sets. I will present a new sharp result on minimum-degree conditions that guarantee small percolating sets and discuss some related open problems.

28 March 2019 (Thursday), 4:00 pm, 418 Machray Hall

Speaker: Andriy Prymak
Title: On illumination of the boundary of a convex body in E^n, n=4,5,6.

Abstract: Let $H_n$ be the minimal number of smaller homothetic copies of an $n$-dimensional convex body required to cover the whole body. Equivalently, $H_n$ can be defined via illumination of the boundary of a convex body by external light sources. It is a simple observation that for an $n$-cube (or $n$-parallelotope) exactly $2^n$ smaller copies are needed, so $H_n\ge 2^n$. The Levi-Hadwiger-Gohber-Markus's conjecture is that $H_n=2^n$ with equality attained only for $n$-parallelotopes.

The best known upper bound in three-dimensional case is $H_3\le 16$ and is due to Papadoperakis. The method is based on the reduction of the illumination problem for a general convex body to that of covering specific sets of relatively simple structure by certain rectangular parallelotopes. We use Papadoperakis' approach to improve approximately by a factor of three the best previously known upper bounds on $H_n$ for $n=4,5,6$. In particular, we show $H_4\le 96$ where the previous bound was $H_4\le 296$.

In the $4$-dimensional case we also obtain a \emph{precise} solution of two related covering problems. Namely, the smallest number of rectangular parallelotopes with sides parallel to the coordinate axes and the sum of dimensions strictly less than $1$ (or $\le1$) that is needed to cover the union of all $2$-dimensional faces of the $4$-dimensional unit cube is $89$ (or $88$, respectively).

This is a joint work with V. Shepelska.

5 April 2019, 3:30 pm, 418 Machray Hall

Speaker: Xiaohong Zhang
Title: Quantum state transfer on graphs

Abstract: Let $G$ be a (weighted) graph on $n$ vertices, and let $M$ be either the adjacency or Laplacian matrix of $G$. Let $U(t) = e^{itM}$. Then $U(t)$ is a complex symmetric unitary matrix. For $1\leq j,k\leq n$, the fidelity of state transfer between vertices $j$ and $k$ at time $t$ is given by $p_{j,k}(t) = \left|(U(t))_{j,k}\right|^2=\left|e_j^TU(t)e_k\right|^2$, which is a number between 0 and 1. There are several interesting phenomena of quantum state transfer that are defined based on the notion of fidelity: perfect state transfer (PST), pretty good state transfer (PGST), and fractional revival (FR).

In this talk, an overview of related results, as well as some useful tools in the analysis will be presented.