CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Structural properties of graphs III

XING SHI CAI, McGill University
The graph structure of a deterministic automaton chosen at random  [PDF]

An n-state deterministic finite automaton over a k-letter alphabet can be seen as a digraph with n vertices which all have k labeled out-arcs. Grusho proved that with high probability in a random k-out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that with high probability the part outside the giant contains at most a few short cycles and mostly consists of tree-like structures, and present a new proof of Grusho’s theorem. Among other things, we pinpoint the phase transition for strong connectivity.

FERDINAND IHRINGER, Justus-Liebig-Universität Gießen
Erdős-Ko-Rado Sets and Semidefinite Programming in Hermitian Polar Spaces  [PDF]

A reflexive Hermitian form over $\mathbb{F}_{q^2}^6$ defines a geometry $\mathsf{H}(5, q^2)$, which consists of points, lines and planes. An Erdős-Ko-Rado set $Y$ of $\mathsf{H}(5, q^2)$ consists of planes, which pairwise meet non-trivially. An interesting problem is to provide an upper bound on $Y$. The analog problem for $\mathsf{H}(2d-1, q^2)$ is open for $d > 3$ odd. We define a coherent configuration on $\mathsf{H}(5, q^2)$ to apply Hobart's semidefinite programming bound. This yields a tight upper bound on $Y$. By the time of the talk it might be clear if this technique extends to the first open case, $\mathsf{H}(9, 4)$.

FIACHRA KNOX, Simon Fraser University
Bounding the spectral radius of an infinite graph  [PDF]

Let $G$ be a connected infinite graph with minimum degree $k$ in which every vertex $v$ admits a non-contractible closed walk of length at most $l$ starting and ending at $v$. We give $a(k, l)$ such that for every such $G$ and every vertex $v_0$ of $G$, the number of closed walks $a_t(v_0)$ which start and end at $v_0$ satsifies $a_t(v_0)\geq a(k, l)^t>2^t(k-1)^{t/2}$ for infinitely many $t\in\mathbb{N}$. Using this inequality we bound the spectral radius of $G$ away from the Ramanujan bound $2\sqrt{k-1}$. This extends a result of Paschke, who proved this for vertex-transitive graphs $G$ satsifying the conditions above.

Graph representatives of positroid strata  [PDF]

The positroid stratification, studied by many authors, is a coarsening of the matroid stratification of the Grassmannian. Each graph (with orientation and edge-ordering) gives a point in the Grassmannian; for a matroid stratum to contain such a point is a well-known forbidden minor condition on the matroid. We show that, by contrast, every positroid stratum contains a graphical representative; indeed, one can choose the graph to be planar. This is despite the fact that the matroid stratum dense in the positroid stratum does not typically contain such a representative (“positroids are not graphic matroids”). Joint work with Allen Knutson.

FRANK RUSKEY, University of Victoria
Simple Venn Diagrams are Hamiltonian  [PDF]

In 1984, Winkler conjectured that every Venn diagram is extendible; i.e., to any $n$-Venn diagram can be added a new curve to obtain a $(n+1)$-Venn diagram. This is equivalent to conjecturing that the planar dual of any Venn diagram is Hamiltonian. It is assumed here that curve intersections are \emph{simple}: at most two curves intersect at any point. We prove a dual result: that is, every Venn diagram itself is Hamiltonian. Here the intersection points of the curves are the vertices of the graph, and the curve segments that connect intersection points are the edges. (co-author: Gara Pruesse.)


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan