CMS 75th+1 Anniversary Summer Meeting

Ottawa, June 7 - 11, 2021   Modern Trends in Graph Theory
Org: Bojan Mohar (Simon Fraser University) and Sergey Norin (McGill University)
[PDF]

A rainbow connectivity threshold for random graph families  [PDF]

Given a family $\mathcal G$ of graphs on a common vertex set $X$, we say that $\mathcal G$ is \emph{rainbow connected} if for every vertex pair $u,v \in X$, there exists a path from $u$ to $v$ that uses at most one edge from each graph of $\mathcal G$. We consider the case that $\mathcal G$ contains $s$ graphs, each sampled randomly from $G(n,p)$, with $n = |X|$ and $p = \frac{c \log n}{sn}$, where $c > 1$ is a constant. We show that there exists a threshold of at most three consecutive integer values such that when $s$ is greater than or equal to this threshold, $\mathcal G$ is a.a.s.~rainbow connected, and when $s$ is below this threshold, $\mathcal G$ is a.a.s.~not rainbow connected. This is joint work with Bojan Mohar.

MICHELLE DELCOURT, Ryerson University
Progress towards Nash-Williams' conjecture on triangle decompositions  [PDF]

Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large, triangle divisible graph on n vertices with minimum degree at least 0.75 n admits a triangle decomposition. In the light of recent results, the fractional version of this problem is of central importance. A fractional triangle decomposition is an assignment of non-negative weights to each triangle in a graph such that the sum of the weights along each edge is precisely one.

We show that for any graph on n vertices with minimum degree at least 0.827327 n admits a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on n vertices with minimum degree at least 0.82733 n admits a triangle decomposition. This is a significant improvement over the previous asymptotic result of Dross showing the existence of fractional triangle decompositions of sufficiently large graphs with minimum degree more than 0.9 n. This is joint work with Luke Postle.

ZDENEK DVORAK, Charles University
Fractional fragility  [PDF]

For a graph parameter $f$ (for example treewidth), the fractional $f$-fragility gives a measure of a distance of a given graph from the graphs on which $f$ is bounded. We survey some structural and algorithmic aspects of this concept.

KRYSTAL GUO, University of Amsterdam
Entanglement of free Fermions on distance-regular graphs  [PDF]

Many physical processes evolving over time on an underlying graph have led to problems in spectral graph theory, including quantum walks. These problems provide new graph invariants and also new applications for theorems about the eigenspaces of graphs. In this talk, we will consider free fermions on vertices of distance-regular graphs are considered. Using concepts from Terwilliger algebras, we study the entanglement Hamiltonian. This is based on joint work with Nicolas Crampé and Luc Vinet.

PAVOL HELL, Simon Fraser University
Signed graph homomorphism problems  [PDF]

Each signed graph H defines a decision problem in which one has to decide if an input signed graph G admits a homomorphism to H. Because a signed graph is an equivalence class under re-signing, this is not exactly a constraint satisfaction problem, but it can be re-cast as an equivalent CSP problem, and hence these problems enjoy dichotomy of polynomial-time solvable versus NP-complete problems. I will discuss the precise classification in the case without lists (conjectured by Brewster, Foucaud, Naserasr and the speaker, and proved by Brewster and Siggers), as well as recent results by Kim and Siggers, and by the speaker jointly with Bok, Brewster, Feder and Jedli\v ckov\' a, on the version with lists. Interesting questions remain open in the list version.

JEANETTE JANSSEN, Dalhousie University
Reconstructing the linear order of a locally connected random graph  [PDF]

Consider the following random graph process. Vertices are sampled from the interval $[0,1]$. Pairs of vertices are then connected (conditionally) independently with probability depending on their distance. Precisely, there is a decreasing function $f:[0,1]\rightarrow [0,1]$, the probability link function, and for a pair of vertices $x,y\in [0,1]$, the connection probability is $f(|x-y|)$. Since vertices are embedded in the line segment, they have a natural ordering. Vertices that are closer to each other in the order are more likely to be connected; thus most connections are local.

The problem we consider is that of retrieving this order from the sampled graph; this may be referred to as graph seriation. We present a randomized graph seriation algorithm that, for a large class of probability functions, yields an ordering with error $O^{*}(\sqrt{n})$ with high probability; we also show that this is the best-possible convergence rate for a large class of algorithms and proof strategies. Under an additional assumption on the probability function, we obtain the vastly better rate $O^{*}(n^{\epsilon})$ for any $\epsilon > 0$.

This is joint work with Aaron Smith.

DANIEL KRAL, Masaryk University
Uniform Turán density of 3-uniform hypergraphs  [PDF]

The uniform Turán density of a hypergraph $H$ is the infimum of all $d$ such that every sufficiently large hypergraph $H_0$ such that every linear size induced subhypergraph of $H_0$ has density at least $d$ contains $H$ as a subhypergraph. In addition to the classification of $3$-uniform hypergraph with uniform Turán density equal to zero by Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77-97], the only additional $3$-uniform hypergraphs whose uniform Turán density is known are $K_4^-$. In this talk, we determine the uniform Turán density of several families of $3$-uniform hypergraphs, in particular, we present a specific family of $3$-uniform hypergraphs with uniform Turán density equal to $1/27$.

GARY MACGILLIVRAY, University of Victoria
Structure of the SDR graph  [PDF]

The SDR graph of a collection $S$ of sets is the graph whose vertices correspond to the systems of distinct representatives (SDRs) of $S$, and where two vertices are adjacent if the corresponding SDRs differ in the representative of exactly one set. The SDR graph is shown to be connected if and only if a Hall-like condition holds, and Hamilton connected when the number of different elements that appear in the sets is greater than twice the number of sets.

This is joint work with Stefan Bard.

BOJAN MOHAR, Simon Fraser University
Many flows in the group connectivity setting  [PDF]

Two well-known results in the world of nowhere-zero flows are Jaeger's 4-flow theorem asserting that every 4-edge-connected graph has a nowhere-zero $Z_2 \times Z_2$-flow and Seymour's 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero $Z_6$-flow. These results were extended by Dvorak et al., proving the existence of exponentially many nowhere-zero flows under the same assumptions. We revisit this setting and provide extensions and simpler proofs of these results.

The concept of a nowhere-zero flow was extended in a significant paper of Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. For a fixed abelian group $\Gamma$, an oriented graph $G = (V,E)$ is called $\Gamma$-\emph{connected} if for every function $f : E \rightarrow \Gamma$ there is a flow $\phi : E \rightarrow \Gamma$ with $\phi(e) \neq f(e)$ for every $e \in E$ (note that taking $f = 0$ forces $\phi$ to be nowhere-zero). Jaeger et al.\ proved that every oriented 3-edge-connected graph is $\Gamma$-connected whenever $|\Gamma| \ge 6$. We prove that there are exponentially many solutions whenever $|\Gamma| \ge 8$. For the group $Z_6$ we prove that for every oriented 3-edge-connected $G = (V,E)$ with $\ell = |E| - |V| \ge 11$ and every $f: E \rightarrow Z_6$, there are at least $2^{ \sqrt{\ell} / \log \ell}$ flows $\phi$ with $\phi(e) \neq f(e)$ for every $e \in E$.

This is joint work with Matt DeVos, Rikke Langhede, and Robert Samal.

JOY MORRIS, University of Lethbridge
Cop Numbers of Generalised Petersen Graphs  [PDF]

It was previously proved by Ball et al. (2015) that the cop number of any generalised Petersen graph is at most $4$. I will present results that explain all of the known generalised Petersen graphs that actually have cop number $4$, and that place them in the context of infinite families. A key consideration is the girth of the graph. This is based on joint work with Harmony Morris, Tigana Runte, and Adrian Skelton.

SERGEY NORIN, McGill University
Fractional extremal function for graph minors  [PDF]

The extremal function of a graph $H$ is the supremum of ratios $|E(G)|/|V(G)|$ taken over non-null graphs $G$ not containing $H$ as a minor. In this talk we introduce a natural fractional variant of the extremal function and discuss its properties.

Based on joint work with Kevin Hendrey and David Wood.

LUKE POSTLE, University of Waterloo
Further progress towards Hadwiger's conjecture  [PDF]

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-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. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^{6})$-colorable.

BRUCE RICHTER, University of Waterloo
Embedding Peano Spaces in Surfaces  [PDF]

It is known that each surface S has a finite set F(S) of minimal finite graphs that do not embed in S. A Peano space is a topological space that is a continuous image of the unit interval. This is equivalent to being a locally connected, connected, compact metric space. We show that a Peano space P embeds in S if and only if P contains one of: a finite graph in F(S); a surface with Euler characteristic larger than that of S; or a generalization of the thumbtack space.

MATEJA SAJNA, University of Ottawa
Finding Euler tours and Euler families in hypergraphs via edge cuts  [PDF]

An Euler tour of a hypergraph $H$ is a closed walk that traverses each edge of $H$ exactly once. The study of Euler tours in hypergraphs was initiated in a 2010 paper by Lonc and Naroski. These authors also proved that the problem of existence of an Euler tour in a general hypergraph (as well as in a 3-uniform hypergraph) is NP-complete. In a 2017 paper, Bahmanian and \v{S}ajna defined a relaxation of the concept of Euler tour, namely, Euler family, which is a collection of closed walks that jointly traverse each edge of the hypergraph exactly once, and showed that the problem of existence of an Euler family in a general hypergraph is polynomial.

In this talk, we show how the problem of existence of an Euler tour (family) in a hypergraph $H$ can be reduced to the analogous problem in some smaller hypergraphs that are derived from $H$ using an edge cut of $H$. In the process, new techniques of edge cut assignments and collapsed hypergraphs will be introduced. Moreover, we shall describe two divide-and-conquer-type algorithms based on these characterizations that construct an Euler tour (family) in a hypergraph if it exists.

This is joint work with Andrew Wagner.

ROBERT SAMAL, Charles University
Random embeddings  [PDF]

An embedding of a connected graph on an orientable surface can be described (up to a homeomorphism) by providing a cyclic permutation for each vertex to describe the ordering of edges incident with the vertex. By choosing each of the permutations uniformly at random we get a random embedding of the given graph.

The study of random embeddings was started by Stahl and White in the 1990's, the main questions were the distribution of genus (equivalently, of the number of faces). The case of a multigraph with a single vertex and with two vertices was completely understood. We extend this to multistars, multigraphs where all edges are incident with a single vertex. We use Stanley's result on enumerating permutations to precisely bound the expected number of faces of a multistar. We apply this to get an estimate on the expected number of faces of a general graph in terms of its degeneracy. We also report on work-in-progress about getting a logarithmic bound on the expected number of faces of a complete graph.

Joint work with Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, and Bojan Mohar.