Vincent Vatter
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
Research Interests
Vincent Vatter has a total of 39 co-authors. Here are the top co-authors by number of shared publications:
- Robert Brignall
Open University UK
12 shared publications - Bruce E. Sagan
Department of Mathematics, Michigan State University, East Lansing, USA
8 shared publications - Nik Ruškuc
University of St Andrews
5 shared publications Michael Albert
Department of Computer Science, University of Otago, Dunedin 9054, New Zealand
4 shared publicationsMichael H. Albert
4 shared publications- Michael Henry Albert
Department of Computer Science University of Otago Dunedin New Zealand
4 shared publications
Latest Publications
- Open Access
- 3 October 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (4) , P4.53
Bounds on the Lettericity of Graphs
Lettericity measures the minimum size of an alphabet needed to represent a graph as a letter graph, where vertices are encoded by letters, and edges are determined by an underlying decoder. We prove that all graphs on $n$ vertices have lettericity at most approximately $n - \tfrac{1}{2} \log_2 n$ and that almost all graphs on $n$ vertices have lettericity at least $n - (2 \log_2 n + 2 \log_2 \log_2 n)$.- 3 October 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (4) , P4.53
Open AccessBounds on the Lettericity of Graphs
Lettericity measures the minimum size of an alphabet needed to represent a graph as a letter graph, where vertices are encoded by letters, and edges are determined by an underlying decoder. We prove that all graphs on $n$ vertices have lettericity at most approximately $n - \tfrac{1}{2} \log_2 n$ and that almost all graphs on $n$ vertices have lettericity at least $n - (2 \log_2 n + 2 \log_2 \log_2 n)$. - 29 August 2024
- Published by Taylor & Francis in Math Horizons
- Vol. 32 (1) , 12-15
The Probability of an Even Product
- 29 August 2024
- Published by Taylor & Francis in Math Horizons
- Vol. 32 (1) , 12-15
The Probability of an Even Product
- 14 February 2024
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 131 (5) , 432
Counting Parity Palindrome Compositions
- 14 February 2024
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 131 (5) , 432
Counting Parity Palindrome Compositions
- 5 October 2023
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 130 (10) , 892
On Erdős’s Proof of the Existence of Cages
- 5 October 2023
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 130 (10) , 892
On Erdős’s Proof of the Existence of Cages
- 1 February 2023
- Published by Taylor & Francis in Math Horizons
- Vol. 30 (3) , 18-19
Penn and Teller Fooled by Parity
On the television show Penn & Teller: Fool Us, magicians attempt to fool Penn Jillette and Teller, themselves long-established magician-comedians with a show in Las Vegas. The prize for those who a...
- 1 February 2023
- Published by Taylor & Francis in Math Horizons
- Vol. 30 (3) , 18-19
Penn and Teller Fooled by Parity
On the television show Penn & Teller: Fool Us, magicians attempt to fool Penn Jillette and Teller, themselves long-established magician-comedians with a show in Las Vegas. The prize for those who a...
- Open Access
- 12 October 2022
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 2 (3)
Labelled well-quasi-order for permutation classes
While the theory of labelled well-quasi-order has received significant attention in the graph setting, it has not yet been considered in the context of permutation patterns. We initiate this study here, and show how labelled well quasi order provides a lens through which to view and extend previous well-quasi-order results in the permutation patterns literature. Connections to the graph setting are emphasised throughout. In particular, we establish that a permutation class is labelled well-quasi-ordered if and only if its corresponding graph class is also labelled well-quasi-ordered.Mathematics Subject Classifications: 05A05, 06A07Keywords: Labelled well-quasi-order, permutation patterns, well-quasi-order
- 12 October 2022
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 2 (3)
Open AccessLabelled well-quasi-order for permutation classes
While the theory of labelled well-quasi-order has received significant attention in the graph setting, it has not yet been considered in the context of permutation patterns. We initiate this study here, and show how labelled well quasi order provides a lens through which to view and extend previous well-quasi-order results in the permutation patterns literature. Connections to the graph setting are emphasised throughout. In particular, we establish that a permutation class is labelled well-quasi-ordered if and only if its corresponding graph class is also labelled well-quasi-ordered.Mathematics Subject Classifications: 05A05, 06A07Keywords: Labelled well-quasi-order, permutation patterns, well-quasi-order
- 1 March 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 309, 215-220
Letter graphs and modular decomposition
- 1 March 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 309, 215-220
Letter graphs and modular decomposition
- 6 July 2021
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 65 (10) , 2610-2614
How Many Pop-Stacks Does It Take To Sort A Permutation?
Pop-stacks are variants of stacks that were introduced by Avis and Newborn in 1981. Coincidentally, a 1982 result of Unger implies that every permutation of length $n$ can be sorted by $n-1$ passes through a deterministic pop-stack. We give a new proof of this result inspired by Knuth’s zero-one principle.- 6 July 2021
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 65 (10) , 2610-2614
How Many Pop-Stacks Does It Take To Sort A Permutation?
Pop-stacks are variants of stacks that were introduced by Avis and Newborn in 1981. Coincidentally, a 1982 result of Unger implies that every permutation of length $n$ can be sorted by $n-1$ passes through a deterministic pop-stack. We give a new proof of this result inspired by Knuth’s zero-one principle.- 28 May 2021
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 128 (6) , 483-499
Bijective Proofs of Proper Coloring Theorems
The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case, and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.
- 28 May 2021
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 128 (6) , 483-499
Bijective Proofs of Proper Coloring Theorems
The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case, and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.
- Open Access
- 2 January 2021
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 128 (1) , 4-24
Containing All Permutations
Numerous versions of the question “what is the shortest object containing all permutations of a given length?” have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions.
- 2 January 2021
- Published by Taylor & Francis in The American Mathematical Monthly
- Vol. 128 (1) , 4-24
Open AccessContaining All Permutations
Numerous versions of the question “what is the shortest object containing all permutations of a given length?” have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions.