Peter Mark Kayll
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Peter Mark Kayll has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
- Bojan Mohar
Department of Mathematics Simon Fraser University Burnaby British Columbia Canada
3 shared publications - Ararat Harutyunyan
Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada
2 shared publications - Michael Morris
University of Montana
2 shared publications Cory Palmer
1 shared publication- Cory Palmer
Department of Mathematical Sciences University of Montana Missoula Montana USA
1 shared publication - Dan Johnston
Trinity College
1 shared publication
Latest Publications
- Open Access
- 31 December 2023
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 18 (2) , 234-243
On Colouring Oriented Graphs of Large Girth
We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^*$ along with a surjective homomorphism $\psi\colon D^* \to D$ such that: (i) girth$(D^*) \geq\ell$; (ii) for every oriented graph $C$ with at most $k$ vertices, there exists a homomorphism from $D^*$ to $C$ if and only if there exists a homomorphism from $D$ to C; and (iii) for every $D$-pointed oriented graph $C$ with at most $k$ vertices and for every homomorphism $\varphi\colon D^* \to C$ there exists a unique homomorphism $f\colon D \to C$ such that $\varphi=f \circ \psi$. Determining the chromatic number of an oriented graph $D$ is equivalent to finding the smallest integer $k$ such that $D$ admits a homomorphism to an order-$k$ tournament, so our main theorem yields results on the girth and chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given $\ell\geq 3$ and $k\geq 5$, we include a construction of an oriented graph with girth $\ell$ and chromatic number $k$.- 31 December 2023
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 18 (2) , 234-243
Open AccessOn Colouring Oriented Graphs of Large Girth
We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^*$ along with a surjective homomorphism $\psi\colon D^* \to D$ such that: (i) girth$(D^*) \geq\ell$; (ii) for every oriented graph $C$ with at most $k$ vertices, there exists a homomorphism from $D^*$ to $C$ if and only if there exists a homomorphism from $D$ to C; and (iii) for every $D$-pointed oriented graph $C$ with at most $k$ vertices and for every homomorphism $\varphi\colon D^* \to C$ there exists a unique homomorphism $f\colon D \to C$ such that $\varphi=f \circ \psi$. Determining the chromatic number of an oriented graph $D$ is equivalent to finding the smallest integer $k$ such that $D$ admits a homomorphism to an order-$k$ tournament, so our main theorem yields results on the girth and chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given $\ell\geq 3$ and $k\geq 5$, we include a construction of an oriented graph with girth $\ell$ and chromatic number $k$. - 1 December 2023
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 131 (2) , 95-111
Deranged Matchings: Proofs and Conjectures
- 1 December 2023
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 131 (2) , 95-111
Deranged Matchings: Proofs and Conjectures
- Open Access
On colouring oriented graphs of large girth
We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^*$ along with a surjective homomorphism $ψ\colon V(D^*) \to V(D)$ such that: (i) girth$(D^*) \geq\ell$; (ii) for every oriented graph $C$ with at most $k$ vertices, there exists a homomorphism from $D^*$ to $C$ if and only if there exists a homomorphism from $D$ to $C$; and (iii) for every $D$-pointed oriented graph $C$ with at most $k$ vertices and for every homomorphism $\varphi\colon V(D^*) \to V(C)$ there exists a unique homomorphism $f\colon V(D) \to V(C)$ such that $\varphi=f \circ ψ$. Determining the oriented chromatic number of an oriented graph $D$ is equivalent to finding the smallest integer $k$ such that $D$ admits a homomorphism to an order-$k$ tournament, so our main theorem yields results on the girth and oriented chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given $\ell\geq 3$ and $k\geq 5$, we include a construction of an oriented graph with girth $\ell$ and oriented chromatic number $k$.Open AccessOn colouring oriented graphs of large girth
We prove that for every oriented graph $D$ and every choice of positive integers $k$ and $\ell$, there exists an oriented graph $D^*$ along with a surjective homomorphism $ψ\colon V(D^*) \to V(D)$ such that: (i) girth$(D^*) \geq\ell$; (ii) for every oriented graph $C$ with at most $k$ vertices, there exists a homomorphism from $D^*$ to $C$ if and only if there exists a homomorphism from $D$ to $C$; and (iii) for every $D$-pointed oriented graph $C$ with at most $k$ vertices and for every homomorphism $\varphi\colon V(D^*) \to V(C)$ there exists a unique homomorphism $f\colon V(D) \to V(C)$ such that $\varphi=f \circ ψ$. Determining the oriented chromatic number of an oriented graph $D$ is equivalent to finding the smallest integer $k$ such that $D$ admits a homomorphism to an order-$k$ tournament, so our main theorem yields results on the girth and oriented chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given $\ell\geq 3$ and $k\geq 5$, we include a construction of an oriented graph with girth $\ell$ and oriented chromatic number $k$. - Open Access
Deranged matchings: proofs and conjectures
We introduce, and partially resolve, a conjecture that brings a three-centuries-old derangements phenomenon and its much younger two-decades-old analogue under the same umbrella. Through a graph-theoretic lens, a derangement is a perfect matching in the complete bipartite graph $K_{n,n}$ with a disjoint perfect matching $M$ removed. Likewise, a deranged matching is a perfect matching in the complete graph $K_{2n}$ minus a perfect matching $M'$. With $\mathrm{pm}(\cdot)$ counting perfect matchings, the elder phenomenon takes the form $\mathrm{pm}(K_{n,n}-M)/\mathrm{pm}(K_{n,n})\to 1/e$ as $n\to\infty$ while its youthful analogue is $\mathrm{pm}(K_{2n}-M')/\mathrm{pm}(K_{2n})\to 1/\sqrt{e}$. These starting graphs are both $2n$-vertex `balanced complete $r$-partite' graphs $K_{r \times {2n}/{r}}$, respectively with $r=2$ and $r=2n$. We conjecture that $\mathrm{pm}(K_{r\times{2n}/r}-M)/\mathrm{pm}(K_{r\times{2n}/r})\sim e^{-r/(2r-2)}$ as $n\to\infty$ and establish several substantive special cases thereof. For just two examples, $r=3$ yields the limit $e^{-3/4}$ while $r=n$ results again in $e^{-1/2}$. Our tools blend combinatorics and analysis in a medley incorporating Inclusion-Exclusion and Tannery's Theorem.Open AccessDeranged matchings: proofs and conjectures
We introduce, and partially resolve, a conjecture that brings a three-centuries-old derangements phenomenon and its much younger two-decades-old analogue under the same umbrella. Through a graph-theoretic lens, a derangement is a perfect matching in the complete bipartite graph $K_{n,n}$ with a disjoint perfect matching $M$ removed. Likewise, a deranged matching is a perfect matching in the complete graph $K_{2n}$ minus a perfect matching $M'$. With $\mathrm{pm}(\cdot)$ counting perfect matchings, the elder phenomenon takes the form $\mathrm{pm}(K_{n,n}-M)/\mathrm{pm}(K_{n,n})\to 1/e$ as $n\to\infty$ while its youthful analogue is $\mathrm{pm}(K_{2n}-M')/\mathrm{pm}(K_{2n})\to 1/\sqrt{e}$. These starting graphs are both $2n$-vertex `balanced complete $r$-partite' graphs $K_{r \times {2n}/{r}}$, respectively with $r=2$ and $r=2n$. We conjecture that $\mathrm{pm}(K_{r\times{2n}/r}-M)/\mathrm{pm}(K_{r\times{2n}/r})\sim e^{-r/(2r-2)}$ as $n\to\infty$ and establish several substantive special cases thereof. For just two examples, $r=3$ yields the limit $e^{-3/4}$ while $r=n$ results again in $e^{-1/2}$. Our tools blend combinatorics and analysis in a medley incorporating Inclusion-Exclusion and Tannery's Theorem. - Open Access
Uniquely $D$-colourable digraphs with large girth II: simplification via generalization
We prove that for every digraph $D$ and every choice of positive integers $k$, $\ell$ there exists a digraph $D^*$ with girth at least $\ell$ together with a surjective acyclic homomorphism $\psi\colon D^*\to D$ such that: (i) for every digraph $C$ of order at most $k$, there exists an acyclic homomorphism $D^*\to C$ if and only if there exists an acyclic homomorphism $D\to C$; and (ii) for every $D$-pointed digraph $C$ of order at most $k$ and every acyclic homomorphism $\varphi\colon D^*\to C$ there exists a unique acyclic homomorphism $f\colon D\to C$ such that $\varphi=f\circ\psi$. This implies the main results in [A. Harutyunyan et al., Uniquely $D$-colourable digraphs with large girth, Canad. J. Math., 64(6) (2012), 1310-1328; MR2994666] analogously with how the work [J. Ne\v{s}et\v{r}il and X. Zhu, On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B, 90(1) (2004), 161-172; MR2041324] generalizes and extends [X. Zhu, Uniquely $H$-colorable graphs with large girth, J. Graph Theory, 23(1) (1996), 33-41; MR1402136].Open AccessUniquely $D$-colourable digraphs with large girth II: simplification via generalization
We prove that for every digraph $D$ and every choice of positive integers $k$, $\ell$ there exists a digraph $D^*$ with girth at least $\ell$ together with a surjective acyclic homomorphism $\psi\colon D^*\to D$ such that: (i) for every digraph $C$ of order at most $k$, there exists an acyclic homomorphism $D^*\to C$ if and only if there exists an acyclic homomorphism $D\to C$; and (ii) for every $D$-pointed digraph $C$ of order at most $k$ and every acyclic homomorphism $\varphi\colon D^*\to C$ there exists a unique acyclic homomorphism $f\colon D\to C$ such that $\varphi=f\circ\psi$. This implies the main results in [A. Harutyunyan et al., Uniquely $D$-colourable digraphs with large girth, Canad. J. Math., 64(6) (2012), 1310-1328; MR2994666] analogously with how the work [J. Ne\v{s}et\v{r}il and X. Zhu, On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B, 90(1) (2004), 161-172; MR2041324] generalizes and extends [X. Zhu, Uniquely $H$-colorable graphs with large girth, J. Graph Theory, 23(1) (1996), 33-41; MR1402136]. - 20 October 2016
- Published by Springer Nature
- p. 171-194
Two Chromatic Conjectures: One for Vertices and One for Edges
- 20 October 2016
- Published by Springer Nature
- p. 171-194
Two Chromatic Conjectures: One for Vertices and One for Edges
- 1 December 2012
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 64 (6) , 1310-1328
Uniquely D-colourable Digraphs with Large Girth
Let C and D be digraphs. A mapping f : V(D) →V(C) is a C-colouring if for every arc uv of D, either f (u) f (v) is an arc of C or f (u) = f (v), and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number r ≥ 1, there are uniquely circularly r-colourable digraphs with arbitrarily large girth.
- 1 December 2012
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 64 (6) , 1310-1328
Uniquely D-colourable Digraphs with Large Girth
Let C and D be digraphs. A mapping f : V(D) →V(C) is a C-colouring if for every arc uv of D, either f (u) f (v) is an arc of C or f (u) = f (v), and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number r ≥ 1, there are uniquely circularly r-colourable digraphs with arbitrarily large girth.
- Open Access
Uniquely D-colourable digraphs with large girth
Let C and D be digraphs. A mapping $f:V(D)\to V(C)$ is a C-colouring if for every arc $uv$ of D, either $f(u)f(v)$ is an arc of C or $f(u)=f(v)$, and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number $r\geq 1$, there are uniquely circularly r-colourable digraphs with arbitrarily large girth.Open AccessUniquely D-colourable digraphs with large girth
Let C and D be digraphs. A mapping $f:V(D)\to V(C)$ is a C-colouring if for every arc $uv$ of D, either $f(u)f(v)$ is an arc of C or $f(u)=f(v)$, and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number $r\geq 1$, there are uniquely circularly r-colourable digraphs with arbitrarily large girth. - 13 April 2010
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 26 (5) , 721-726
König–Egerváry Graphs are Non-Edmonds
- 13 April 2010
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 26 (5) , 721-726
König–Egerváry Graphs are Non-Edmonds
- Open Access
- 11 December 2009
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 4 (2)
Another short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings
How many perfect matchings are contained in a given bipartite graph? An exercise in Godsil's 1993 \textit{Algebraic Combinatorics} solicits proof that this question's answer is an integral involving a certain rook polynomial. Though not widely known, this result appears implicitly in Riordan's 1958 \textit{An Introduction to Combinatorial Analysis}. It was stated more explicitly and proved independently by S.A.~Joni and G.-C.~Rota [\textit{JCTA} \textbf{29} (1980), 59--73] and C.D.~Godsil [\textit{Combinatorica} \textbf{1} (1981), 257--262]. Another generation later, perhaps it's time both to simplify the proof and to broaden the formula's reach.
- 11 December 2009
- Published by University of Calgary in Contributions to Discrete Mathematics
- Vol. 4 (2)
Open AccessAnother short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings
How many perfect matchings are contained in a given bipartite graph? An exercise in Godsil's 1993 \textit{Algebraic Combinatorics} solicits proof that this question's answer is an integral involving a certain rook polynomial. Though not widely known, this result appears implicitly in Riordan's 1958 \textit{An Introduction to Combinatorial Analysis}. It was stated more explicitly and proved independently by S.A.~Joni and G.-C.~Rota [\textit{JCTA} \textbf{29} (1980), 59--73] and C.D.~Godsil [\textit{Combinatorica} \textbf{1} (1981), 257--262]. Another generation later, perhaps it's time both to simplify the proof and to broaden the formula's reach.