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.

Subscription to the calendar is available via: https://www.google.com/calendar/ical/4aq25ijhgs0tb19k9cni79ucps%40group.calendar.google.com/public/basic.ics

Schedules for past seminars are available here.

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 |

**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.

**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.

**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.

**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.