Online Talk: Daniel Slilaty

Monday, May 31, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Slilaty, Wright State University
Orientations of golden-mean matroids

 
Abstract:

Tutte proved that a binary matroid is representable over some field of characteristic other than 2 if and only if the matroid is regular. His result inspired the discovery of analogs for $GF(3)$-representable matroids by Whittle, $GF(4)$-representable matroids by Vertigan as well as Pendavingh and Van Zwam, and $GF(5)$-representable matroids by Pendavingh and Van Zwam.

Bland and Las Vergnas proved that a binary matroid’s orientations correspond to its regular representations. (Minty’s result on digraphoids is closely related.) Lee and Scobee proved that a $GF(3)$-representable matroid’s orientations correspond to its dyadic representations. In this talk we will explore orientations of $GF(4)$-representable matroids. A natural partial field to use is the golden-mean partial field; however, not every orientation of a $GF(4)$-representable matroid comes from a golden-mean representation. For example, $U_{3,6}$ has 372 orientations but only 12 of them come from golden-mean representations. We will give a combinatorial characterization of those orientations of $GF(4)$-representable matroids which do come from golden-mean representations and show that these orientations correspond one-to-one to the golden-mean representations.

Joint work with Jakayla Robbins.

Online Talk: Bertrand Guenin

Monday, May 17, 3pm ET (8pm BST, 7am Tue NZST)
Bertrand Guenin, University of Waterloo
Graphs with the same even cycles

 
Abstract:
In 1933 Whitney described the relationship between pairs of graphs with the same set of cycles (here we view cycles as sets of edges). A natural question is to try to understand the relationship between pairs of graphs with the same set of even cycles (a cycle is even if it contains an even number of edges). We show that there is a nice answer to this question under some connectivity assumptions and we explain the relevance of this question to matroid theory.
 
This is joint work with: Cheolwon Heo, Zouhaier Ferchiou, Irene Pivotto.

Oriented matroid localizations



Oriented matroid theory is both a branch of matroid theory and a branch of topology. One can prove results by treating them as signed versions of results in matroid theory, or, thanks to the Topological Representation Theorem, one can treat them as statements about arrangements of pseudospheres. Here I’d like to discuss a result of Michel Las Vergnas on localizations of oriented matroids, which he proved as a signed version of a matroid result by Henry Crapo, and a new proof from the topological perspective.

The topological proof has a geometrically intuitive feel that, I think, is harder to see in the matroid proof. On the other hand, the matroid proof lends itself to generalization: for instance, Ting Su ([3]) has a nice result showing the extent to which the result generalizes to matroids over hyperfields.

Notation: ${\mathcal{C}}^*$ denotes the signed cocircuit set of an oriented matroid $M$ on elements $E$. The set $\{0,+,-\}$ is a poset with maximal elements $+$ and $-$ and unique minimal element $0$. For $x,y\in\{0,+,-\}$, $x\boxplus y$ is $\{\max(x,y)\}$ if $\{x,y\}\neq\{+,-\}$, and $\{0,+,-\}$ if $\{x,y\}=\{+,-\}$.The set $\{0,+,-\}^E$ is a poset, ordered componentwise, and the sum $X\boxplus Y$ of two sign vectors is componentwise sum. 

When we extend $X\in\{0,+,-\}^E$ to  $X’\in\{0,+,-\}^{E\cup \{f\}}$ by setting $X'(f)=\alpha$, we’ll denote the extension by $Xf^\alpha$. 

 A topological representation of an oriented matroid $M$ on elements $E$ is given as $(S_e:e\in E)$, where each $S_e$ is a pseudosphere in the sphere $S^{{\mathrm{rank}}(M)-1}$. We typically omit the signs on the pseudospheres when they don’t come up in our discussion. When we refer to the cells of a topological representation, we mean cells in the cell decomposition of $S^{{\mathrm{rank}}(M)-1}$ given by the representation.

If $M$ is either a matroid or an oriented matroid with elements $E$ and $f\not\in E$, a proper single-element extension of $M$ by $f$ is a matroid resp. oriented matroid $M’$ on elements $E\cup \{f\}$ such that the deletion $M\backslash f$ is $M$ and $f$ is neither a loop nor a coloop in $M’$.

If $M$ is a matroid and $X\subseteq E$ is a cocircuit of $M$, then either $X$ or $X\cup\{f\}$ is a cocircuit of $M’$. If $M$ is an oriented matroid and $X\in\{0,+,-\}^E$ is a signed cocircuit of $M$, then $X$ has a unique extension to a signed cocircuit $Xf^{\sigma(X)}$ of $M’$. The function $\sigma:  {\mathcal{C}}^*\to \{0,+,-\}$ is called the localization of the extension $M’$. For instance, Figure 1 shows a topological representation of a rank 3 oriented matroid $M$ by an element $M$ and values of $\sigma(X)$ at some signed cocircuits $X$.

Pondering Figure 1, it seems clear how to characterize $ {\mathcal{C}}^*(M’)$ in terms of the localization.

  • For each $X\in  {\mathcal{C}}^*$, we have its extension $Xf^{\sigma(X)}$ to a signed cocircuit of $M’$.
  • We get additional signed cocircuits of $M’$ from certain modular pairs $X_1, X_2$ of signed cocircuits of $M$. The topological interpretation of modularity is that $X_1, X_2$ is a modular pair of signed cocircuits if the corresponding 0-cells in a topological representation lie on a common pseudocircle of the representation. We’ll call a modular pair $X_1, X_2$ neighbors of they’re the ends of a 1-cell of the topological representation. Whenever $X_1$ and $X_2$ are neighbors and $\sigma(X_1)=-\sigma(X_2)\neq 0$, we get a signed circuit $(X_1\circ X_2)f^0$ of $M’$. Two examples of this arise in the lower right of Figure 1.

 For matroids, the unsigned version of this characterization takes some work (see [2]). For oriented matroids, it is a triviality. Each signed cocircuit of $M’$ corresponds to a 0-cell in a pseudocircle not contained in the $f$-pseudosphere $S_f$, and each such pseudocircle intersects $S_f$ in exactly two points. For each pseudocircle, the 0-cells not contained in $S_f$ correspond to signed cocircuits $X^{\sigma(X)}$ with $\sigma(X)\neq 0$, and the 0-cells contained in $S_f$ correspond to either signed cocircuits $X^{\sigma(X)}$ with $\sigma(X)= 0$ or signed cocircuits  $(X_1\circ X_2)f^0$.

The result of Las Vergnas that we’ll focus on is a characterization of localizations by reduction to rank 2. For rank 1 oriented matroids or rank 2 oriented matroids on 2 elements, a function $\sigma: {\mathcal{C}}^*\to\{0,+,-\}$ is a localization if it is nonzero and symmetric, i.e. $\sigma(X)=-\sigma(-X)$. For rank 2 oriented matroids on 3 elements, there are three nonzero symmetric functions $\sigma: {\mathcal{C}}^*\to\{0,+,-\}$ which are not localizations: they are shown in Figure 2.

If $M$ has rank at least 2 and at least 3 elements, then a function on $ {\mathcal{C}}^*$ induces a function on $ {\mathcal{C}}^*(N)$ for each minor $N$ of $M$. 

Theorem 1 ([2]) Let $M$ be an oriented matroid of rank at least 2 on at least 3 elements. A nonzero function $ {\mathcal{C}}^*\to\{0,+,-\}$ is a localization if and only if each induced function on a rank 2 minor with 3 elements is either 0 or a localization.

 Las Vergnas proved Theorem 1 by building on an unsigned version due to Crapo ([1]). Their proofs are combinatorially elegant, but I doubt anyone will ever try to summarize the full oriented matroid proof in a few short paragraphs. In contrast, I’ll attempt that very feat now for a topological proof.

 Let $\sigma:  {\mathcal{C}}^*\to\{0,+,-\}$ be a nonzero function that induces a localization or zero function on each rank 2 minor with 3 elements. Because rank 2 oriented matroids are realizable, it’s easy to check that $\sigma$ induces a localization or zero function on each rank 2 minor. Topologically, this says that the restriction of $\sigma$ to any one pseudocircle in a topological representation looks like a localization. If we treat the 0-cells and 1-cells of a  topological representation as a graph $G(M)$, this tells us that $\sigma$ behaves like a localization along many paths in $G(M)$.

 The function $\sigma$ defines a candidate ${\mathcal{D}}^*\subseteq \{0,+,-\}^{E\cup \{f\}}$ for the signed cocircuit set of an extension, as we’ve already described. The only difficulty in proving that  ${\mathcal{D}}^*$ is indeed the signed cocircuit set of an extension is in showing that ${\mathcal{D}}^*$ satisfies  the Elimination Axiom. A topological way to interpret the Elimination Axiom is that, for every pair of non-antipodal 0-cells  $X$ and $Y$ in a symmetric  topological representation of $M$, if $S_e$ is a pseudosphere of the arrangement, $X$ is on the negative side of $S_e$, and $Y$ is on the positive  side of $S_e$, then the intersection of $S_e$ with the convex hull of $X$ and $Y$ contains a 0-cell. (Here the convex hull of a set $T$ of cells is the set of cells in the smallest intersection of closed pseudohemispheres containing $T$.) Put more graph-theoretically, there is a path $\gamma$ from $X$ to $Y$ in the part of $G(M)$ that lies in the convex hull of $X$ and $Y$  such that $\gamma$ has a vertex in $S_e$.

 Fix a topological representation of $M$. When we move from $ {\mathcal{C}}^*$ to ${\mathcal{D}}^*$, we don’t have a pseudosphere representing our new element $f$, but we have a function $\sigma$ that purports to tell us on which side of such a pseudosphere each 0-cell would lie. This characterization is convincing along any one pseudocircle. This, together with induction on ${\mathrm{rank}}(M)$, gives us a path $\gamma_0$ in $G(M)$ from $X$ to $Y$ that intersects $S_e$ and is not far from being in the convex hull of $X$ and $Y$: in particular, $\sigma$ takes values in $\sigma(X)\boxplus\sigma(Y)$ along $\gamma_0$. The idea of $\gamma_0$ is given in Figure 3.

Both endpoints of $\gamma_0$ lie in the convex hull of $X$ and $Y$. If part of $\gamma_0$ is not in the convex hull of $X$ and $Y$, then there is a bounding pseudosphere $S_g$ for this convex hull such that $\gamma_0$ crosses to the wrong side of $S_g$ at some point $X’$, then returns to the correct side of $S_g$ at some point $Y’$. By induction on rank we can find a path from $X’$ to $Y’$ in $S_g$ that lies in the convex hull of $X’$ and $Y’$. We then get a new path $\gamma_1$ from $\gamma_0$ by replacing the part of $\gamma_0$ between $X’$ and $Y’$ with our new path in $S_g$. This path $\gamma_1$ no longer strays to the wrong side of $S_g$. By repeating this operation of lopping off parts of the graph not in the convex hull of $X$ and $Y$, we arrive at our desired path $\gamma$.

 Now let’s get to a more detailed exposition of the proof (but with proofs of lemmas omitted). 

Polytopal sets

Definition: Let $A\subseteq E$ and $Z\in\{0,+,-\}^A$. The convex set $C_Z$ in $ {\mathcal{C}}^*$ is defined to be $\{Z’\in  {\mathcal{C}}^*: Z'(e)\leq Z(e)\mbox{ for each $e\in A$}\}$.  A vertex of $C_Z$ is a $V\in C_Z-\{0\}$ such that $V^0\cap A$ has rank ${\mathrm{rank}}(M)-1$.

 In a topological representation of $M$, $C_Z$ corresponds to an intersection of closed pseudohemispheres, and its vertices are the “corners” of this intersection.  For example, Figure 4 shows convex sets in two oriented matroids, as well as the vertices of each.

Definition: Let $S$ be a set of covectors of $M$. The convex hull ${\mathrm{conv}}(S)$ is the smallest convex set $ C_Z$ containing $S$.  A convex set $C_Z$ is polytopal if $C_Z$ is the convex hull of its vertex set.

For instance, in the oriented matroid pictured in Figure 4 the convex set $C_{d^+e^+}$ is not polytopal, because the convex hull of its vertex set is $\{0, V_1, V_2\}$. The convex set $C_{a^+b^+c^+}$ is polytopal.

Lemma 1: If $X\neq -Y$ are signed cocircuits of $M$ then ${\mathrm{conv}}(\{X,Y\})$ is polytopal.

Our interest in polytopal sets comes from the following lemma to the proof of of Theorem 1.

Lemma 2: Let $C$ be a polytopal set and $Y$ a cocircuit in the interior of $C$. Let $\sigma$ be the localization of an extension of $M$. 

  1. If $\sigma(Y)=\epsilon\neq 0$ then there is a vertex $Z$ of $C$ so that $\sigma(Z)=\epsilon$.
  2. If $\sigma(Y)= 0$ then either $\sigma(X)=0$ for every cocircuit $X\in C$ or there are vertices $X_+$ and $X_-$ of $C$ so that $\sigma(X_+)=+$ and $\sigma(X_-)=-$.

This is analogous to the observation  that if a linear function has nonnegative value on all vertices of a convex polytope then it has nonnegative value on the entire polytope, and if a linear function has value 0 onsome interior point of a convex polytope then either it has value 0 on all vertices or it attains both negative and positive values at vertices.

Good paths

Let $M$ have rank $r$. In the cell decomposition of $S^{r-1}$ given by a topological representation of $M $ the 0-cells correspond to signed cocircuits, which are covectors  $X$ with ${\mathrm{rank}}(X^0)=r-1$, and the 1-cells correspond to  covectors  $X$ with ${\mathrm{rank}}(X^0)=r-2$. Thus these two types of covectors form a graph $G(M )$ with vertex set ${\mathcal{C}}^*$. 

Our first abuse of graph terminology is to define $G(M)$ as a single set of covectors, rather than as a set of vertices together with a set of edges. Our second abuse of terminology is to define a path in $G(M)$ as a subset $S$ of $G(M)$ (containing both vertices and edges) rather than as a sequence of edges.

Definition: An edge in $G(M)$ is a non-minimal element of $G(M)$. The endpoints of an edge $X$ are the two elements of ${\mathcal{C}}^*$ that are less than $X$.  A path in $G(M)$ from $X$ to $Y$ is a subset of $G(M)$ of the form $\{X=X_0,X_1, \ldots, X_{2k}=Y\}$, where each $X_i$ with $i$ odd is an edge with endpoints $X_{i-1}$ and $X_{i+1}$. 

 For any path $\gamma$ we let $\gamma^0=\gamma\cap{\mathcal{C}}^*$. We’ll avoid calling elements of $\gamma^0$ “vertices” so as not to confuse vertices of a graph with vertices of a polytopal set.

Let $\sigma:{\mathcal{C}}^*\to\{0,+,-\}$, and let $X,Y\in{\mathcal{C}}^*$ such that $X\neq -Y$. A path $\gamma$ in $G(M )$ from $X$ to $Y$ is  good with respect to $\sigma$ if $\gamma\subseteq{\mathrm{conv}}(X,Y)$ and, for each $Z\in\gamma^0$, $\sigma(Z)\in(\sigma(X)\boxplus\sigma(Y))\cup\{0\}$.

Definition: A pair $\gamma_+, \gamma_-$ of paths in $G(M)$ from $X$ to $Y$ is a good path pair with respect to $\sigma$ if $\gamma_+\cup\gamma_-\subseteq {\mathrm{conv}}(X,Y)$, $\sigma(Z)\in\{0,+\}$ for each $Z\in \gamma_+^0$, and $\sigma(Z)\in\{0,-\}$ for each $Z\in \gamma_-^0$. A pair $\gamma_+, \gamma_-$ of paths in $G(M)$ from $X$ to $Y$ is a good path pair with respect to $\sigma$ if $\gamma_+\cup\gamma_-\subseteq {\mathrm{conv}}(X,Y)$, $\sigma(Z)\in\{0,+\}$ for each $Z\in \gamma_+^0$, and $\sigma(Z)\in\{0,-\}$ for each $Z\in \gamma_-^0$.

The left side of Figure 5 shows a good path from $X_1$ to $X_2$ in a case with $\sigma(X_1)=\sigma(X_2)\neq 0$. The right side of Figure 5 shows a good path pair from $X_1$ to $X_2$ in a case with $\sigma(X_1)=\sigma(X_2)=0$.

Lemma 3: Let $\sigma:  {\mathcal{C}} ^*\to \{0,+,-\}$ satisfy all of the following.

  • $\sigma(-X)=-\sigma(X)$ for all $X$. 
  • $\sigma(-X)=-\sigma(X)$ for all $X$.
  • For each $X_1,X_2\in  {\mathcal{C}} ^*$ with $X_1\neq -X_2$ and $\sigma(X_1)\boxplus\sigma(X_2)\neq \{0\}$, there is a good path from $X_1$ to $X_2$. 
  • For each $X_1,X_2\in  {\mathcal{C}} ^*$ with $X_1\neq -X_2$ and $\sigma(X_1)=\sigma(X_2)= 0$,  there is either a good path  from $X_1$ to $X_2$ or a good path pair from $X_1$ to $X_2$. 

 Then $\sigma$ is a localization.

As noted earlier, the only issue in proving this lemma is verifying that the  set ${\mathcal{D}}^*$ resulting from $\sigma$ satisfies the Elimination Axiom. This follows in various cases from the same observations about a good path $\gamma$ from $X_1$ to $X_2$: 

  • if $\sigma(X_1)=-\sigma(X_2)\neq 0$ then at some point on the path the value of $\sigma$ changes, leading to an elimination of $f$ between $X_1f^{\sigma(X_1)}$ and $X_2f^{\sigma(X_2)}$, and
  •  if for some $e$ we have $X_1(e)=-X_2(e)\neq 0$  then at some point on the path there is a $Z\in\gamma^0$ with $Z(e)=0$.  Then $Zf^{\sigma(Z)}$ eliminates $e$ between $X_1f^{\sigma(X_1)}$ and $X_2f^{\sigma(X_2)}$.

 Definition: Let $X,Y\in{\mathcal{C}}^*$ with $X\neq -Y$. A  preliminary path between $X$ and $Y$ is a path $\phi\subseteq G(M )\cap C_{(X^0\cap Y^0)^0}$ such that $\sigma(Z)\in(\sigma(X)\boxplus\sigma(Y))\cup\{0\}$ for each $Z\in\phi^0$. A  preliminary path pair  between $X$ and $Y$ is a pair $\phi_+, \phi_-\subseteq G(M )\cap C_{(X^0\cap Y^0)^0}$ of paths between $X$ and $Y$ such that $\sigma(Z)\in(\sigma(X)\boxplus\sigma(Y))\cup\{0\}$ for each $Z\in\phi_+^0\cup\phi_-^0$.

 Definition: For $X,Y\in\{0,+,-\}^E$, the seperation set $S(X,Y)$ is $\{e:X(e)=-Y(e)\neq 0\}$.

Let $\gamma$ be a path from $X$ to $Y$ in $G(M )$. Define 

$$S(\gamma)=\bigcup_{Z\in\gamma^0}(S(X,Z)\cup S(Y,Z))\backslash S(X,Y)$$

A  good path path between $X$ and $Y$ is a preliminary path $\gamma$ such that $S(\gamma)=\emptyset$. A good path pair between $X$ and $Y$ is a preliminary path pair  $\gamma_+,\gamma_-$ such that $S(\gamma_+)=S(\gamma_-)=\emptyset$.

Lemma 4: Let $\sigma:{\mathcal{C}} ^*\to\{0,+,-\}$ be a function such that every restriction to a rank 2 minor is a localization. Let $X,Y\in{\mathcal{C}}^*$ with $X\neq -Y$ 

  •  If $\sigma(X)\boxplus\sigma(Y)\neq\{0\}$ then there is a preliminary path  between $X$ and $Y$.
  • If $\sigma(X)\boxplus\sigma(Y)=\{0\}$ then there is either  a preliminary path between $X$ and $Y$ or a preliminary path pair between $X$ and $Y$.

Figure 1 illustrates the construction of a preliminary path. The vertex $\tilde Y$ is the vertex $Z$ given in the first part of Lemma 4.

Now we can prove the hard direction of Theorem 1.  We induct on rank, with the rank 1 and rank 2 cases already discussed. To prove the inductive step we use Lemma 3. Let $X,Y\in{\mathcal{C}}^*$  with $X\neq -Y$.  By Lemma 4, either there is a prelimary path $\phi$ between $X$ and $Y$, or $\sigma(X)\boxplus\sigma(Y)=\{0\}$ and there is a preliminary path pair $\phi_+,\phi_-$  between $X$ and $Y$ .

If $S(\phi)=\emptyset$ in the former case, then $\phi$ is our desired good path, and if  $S(\phi_+)=S(\phi_-)=\emptyset$ in the latter case, then $\phi_+,\phi_-$ is our desired good path pair. So the remainder of the proof shows how to reduce $S(\phi)$ resp. $S(\phi_+)\cup S(\phi_-)$ while maintaining the property of being a preliminary path or path pair.

Case 1: $\sigma(X)\boxplus\sigma(Y)\neq\{0\}$. In any topological representation of $M $, the path $\phi$ crosses $S_e^0$ in at least two points. If $Z_1$ and $Z_2$ are the first and last crossings, then we use the induction hypothesis in $M /e$ to get a good path $\nu$ from $Z_1$ to $Z_2$. 

Let $\phi’$ be the path obtained from $\phi$ by replacing the part of $\phi$ between $Z_1$ and $Z_2$ with $\nu$. Then $S(\phi’)\subseteq S(\phi)\backslash s$, because $\nu$ is a good path with $Z(s)=0$ for all $Z\in\nu^0$, and $\nu$ has replaced all the elements of $\phi$ that have the wrong sign on $s$. Also, elements of $(\phi’)^0$ satisfy the conditions for $\phi’$ to be a preliminary path  because elements of both $\phi^0$ and $\nu^0$ satisfy these conditions.

Case 2: $\sigma(X)\boxplus\sigma(Y)=\{0\}$ and there is a preliminary path $\phi$ between $X$ and $Y$. Let $s\in S(\phi)$. Once again we let $Z_1$ and $Z_2$ be the first and last points where $\phi$ crosses $S_e^0$. The induction hypothesis tells us that either there is a good path $\nu$  from $Z_1$ to $Z_2$ or there is a good path pair $\nu_+, \nu_-$ from $Z_1$ to $Z_2$.

In the former case, once again we let $\phi’$ be the path obtained from $\phi$ by replacing the part of $\phi$ between $Z_1$ and $Z_2$ with $\nu$. Then $S(\phi’)\subseteq S(\phi)\backslash s$, and elements of $(\phi’)^0$ satisfy the conditions for $\phi’$ to be a preliminary path  because elements of both $\phi^0$ and $\nu^0$ satisfy these conditions.

In the latter case we let $\phi_+$ be the path obtained from $\phi$ by replacing the part of $\phi$ between $Z_1$ and $Z_2$ with $\nu_+$, and we let $\phi_-$ be the path obtained from $\phi$ by replacing the part of $\phi$ between $Z_1$ and $Z_2$ with $\nu_-$. Then $S(\phi_-)\cup S(\phi_+)\subseteq S(\phi)\backslash s$,  and elements of $\phi_+^0$ and $\phi_-^0$ satisfy the conditions for $\phi_+,\phi_-$ to be a preliminary path pair  because elements of $\phi^0$, $\nu_+^0$, and $\nu_-^0$ satisfy these conditions.

Case 3:  $\sigma(X)\boxplus\sigma(Y)=\{0\}$ and there is a preliminary path pair $\phi_+,\phi_-$  between $X$ and $Y$. Let $s\in S(\phi_+)\cup s(\phi_-)$. If $s\in S(\phi_+)$, the same argument as in Case 1 lets us modify $\phi_+$ to get a  path $\phi’_{+}$ between $X$ and $Y$ such that $S(\phi’_{+})\subseteq S(\phi_+)\backslash s$ and $\phi’_+, \phi_-$ is a preliminary path pair.  Similarly if $s\in S(\phi_-)$, we can modify $\phi_-$ to get a path $\phi’_{1}$ between $X$ and $Y$ such that $S(\phi’_{-})\subseteq S(\phi_-)\backslash s$  and $\phi_+, \phi’_-$ is a preliminary path pair.  

Bibliography

  1. Crapo, Henry H. Single-element extensions of matroids.  J. Res. Nat. Bur. Standards Sect. B, 69B:55–65 (1965)
  2. Las Vergnas, Michel. Extensions ponctuelles d’une geometrie combinatoire orientee. In Problemes combinatoires et theorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 265-270. CNRS, Paris, 1978.
  3. Su, Ting.  Extensions of weak matroids over skew tracts and strong matroids over stringent skew hyperfields. arXiv:2012.05683 (2020).

 

Online Talk: Sophie Spirkl

Monday, May 10, 3pm ET (8pm BST, 7am Tue NZST)
Sophie Spirkl, University of Waterloo
The complexity of list-5-colouring H-free graphs

 
Abstract:
A $k$-list-assignment for a graph $G$ is a function $L$ from $V(G)$ to subsets of $\{1, …, k\}$. The list-$k$-colouring problem asks, given $G$ and a $k$-list-assignment $L$, is there a colouring $f$ of $G$ with $f(v)$ in $L(v)$ for all $v$ in $V(G)$? This generalizes the $k$-colouring problem (where we use $L(v) = \{1, …, k\}$ for every vertex).
 
For $k$ at least $3$, both $k$-colouring and list-$k$-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to $H$-free graphs (for a fixed $H$, excluded as an induced subgraph).
 
I will present an algorithm for list-$5$-colouring restricted to $H$-free graphs for all $H$ which consist of connected components each of which is a $3$-vertex path. This, together with previous results, gives a complete answer to the question, “for which $H$ is list-$5$-colouring restricted to $H$-free graphs NP-hard?”
 
Joint work with Sepehr Hajebi and Yanjia Li.