# Robert Brignall

### Senior Lecturer in Combinatorics

## WELCOME!

I am a Senior Lecturer in Combinatorics in the School of Mathematics and Statistics at The Open University. My research interests primarily focus on the study of infinite antichains, well-quasi-ordering, permutation patterns, and the interplay between permutation patterns and similar concepts in graph theory. You may read more about my research, view my list of publications or my list of talks.

I am the school's Director of Research, and I also organise our Seminar Series.

Previously, I was a research fellow in the Department of Mathematics at the University of Bristol, and before that I was a PhD student in the School of Mathematics and Statistics at the University of St Andrews.

In the past, I founded the Bristol
Combinatorics Seminar, I was on the organising committees for *Techniques and
Problems in Graph Theory*, Permutation Patterns
2010 and *Permutation Patterns
2011*, and I chaired the local organising committee for Permutation Patterns 2015. I am on the program committee for Permutation Patterns 2019.

Beyond mathematics, I occasionally sing.

## RESEARCH

My research interests broadly lie in the study of combinatorial and relational structures, in a blend of structural, extremal and enumerative combinatorics. My background is in the study of permutation containment and avoidance, where enumeration is the main game. However, the structural study of permutations can often be translated to other combinatorial objects, most notably graphs, where the consequences can be wide-ranging. Currently, I am especially investigating the question of well-quasi-ordering in combinatorial objects and the corresponding construction of infinite antichains, but I also have ongoing projects in permutation enumeration, and structural graph theory.

I submitted my PhD Thesis, entitled "Simplicity in Relational Structures and its Application to Permutation Classes", in July 2007, and successfully defended it in October 2007. My external examiner was Einar Steingrímsson (Strathclyde University), my internal Steve Linton. My PhD was written whilst in the School of Mathematics and Statistics at the University of St Andrews, was supervised by Prof Nikola Ruškuc, and was funded by EPSRC.

#### Research students

- Olivia Jeans (2017-) [second supervisor, part time]
- James Fraser (2016-) [second supervisor]
- David Marchant (2016-) [part time]
- James Tuite (2015-) [second supervisor, part time]
- Jakub Sliacan (2015-2018). [Thesis]
- David Bevan (2012-2015). [Thesis]

#### Grants

In Opinion 117, Doron Zeilberger (my academic grandfather!) suggested more people should upload grant bids, so here are mine.- [FUNDED] EPSRC First Grant, EP/J006130/1, £91,797, 1st October 2012 -- 30th September 2013.
*Infinite Antichains of Combinatorial Structures*.

[Proposal] [GoW] - [FUNDED] LMS Conference Grants (Scheme 1), £560, 30th January 2013.
*Winter Combinatorics Meeting*, held at The Open University.

[Proposal]. - [NOT FUNDED] ERC Starting Grant, 2014. [Part B2]
- [FUNDED] LMS Conference Grants (Scheme 1), £2,000, 11th--12th September 2014.
*Valediction to Jeremy Gray*, held at Mercure Parkside Hotel, Milton Keynes.

[Proposal]. - [FUNDED] LMS Conference Grants (Scheme 1), £1,908, 15th--19th June 2015.
*Permutation Patterns 2015*, held at De Morgan House, London.

[Proposal]. - [NOT FUNDED] EPSRC Standard Grant, 2015. [Proposal]

#### Conference Organisation

- Local organising committee, Winter Combinatorics Meeting, Open University, annually 2011-2016.
- Chair of Local Organising Committee, Permutation Patterns 2015, De Morgan House, London, 15-19 June 2015.
- Organising Committee, Permutation Patterns 2011, California Polytechnic University, San Luis Obispo, USA, 20-24 June 2011.
- Organising Committee, Permutation Patterns 2010, Dartmouth College, USA, 9-13 August 2010.
- Local organising committee, Techniques and Problems in Graph Theory, University of Bristol, 1-3 July 2009.

#### Editing

- 2015-, Australasian Journal of Combinatorics (AJC): Managing Editor.
- 2015-16: Guest editor for the special issue for Permutation Patterns 2015.
*Discrete Mathematics and Theoretical Computer Science*, Volume 18 No. 2 (2016). - 2010-11: Guest editor for the proceedings of Permutation Patterns 2010.
*Pure Mathematics and Applications*, Volume 22 No. 2 (2011).

#### Other Activities

- Review for the LMS Newsletter of
*Alex's Adventures in Numberland*by Alex Bellos. [PDF] [Newsletter]

A version also appeared in Plus Magazine. [Plus] - Read my MathSciNet Reviews.
- Referee for: Annals of Combinatorics, Discrete Applied Mathematics, Discrete Mathematics, Electronic Journal of Combinatorics, Graphs and Combinatorics, Journal of Combinatorial Theory Series A, Journal of Combinatorics, LMS Lecture Note Series, Mathematika, Pure Mathematics and Applications.

#### List of Coauthors

- Michael Albert, Mike Atkinson, Aistis Atminas, David Bevan, Hojin Choi, Shalosh B. Ekhad, Andrew Elvey Price, Michael Engen, Nicholas Georgiou, Sophie Huczynska, Vít Jelínek, Jisu Jeong, Nicholas Korpelainen, Jan Kynčl, Vadim Lozin, David Marchant, Sang-il Oum, Jay Pantone, Nik Ruškuc, Jakub Sliačan, Rebecca Smith, Juraj Stacho, Vincent Vatter, Rob Waters, Julian West.

## PUBLICATIONS

#### Submitted Papers

- Brignall, R., and Sliačan, J., Combinatorial specifications for juxtapositions of permutation classes.

[PDF] [BibTeX] [Abstract]We show that, given a suitable combinatorial specification for a permutation class \(\mathcal{C}\), one can obtain a specification for the juxtaposition (on either side) of \(\mathcal{C}\) with Av(21) or Av(12), and that if the enumeration for \(\mathcal{C}\) is given by a rational or algebraic generating function, so is the enumeration for the juxtaposition. Furthermore this process can be iterated, thereby providing an effective method to enumerate any "skinny" \(k\times 1\) grid class in which at most one cell is non-monotone, with a guarantee on the nature of the enumeration given the nature of the enumeration of the non-monotone cell.@article{bs:context-free, AUTHOR = {Brignall, R. and Slia\v{c}an, J.}, TITLE = {Combinatorial specifications for juxtapositions of permutation classes}, NOTE = {Submitted}, }

- Brignall, R., Jelínek, V., Kynčl, J., and Marchant, D., Zeros of the Möbius function of permutations.

[PDF] [BibTeX] [Abstract]We show that if a permutation \(\pi\) contains two intervals of length 2, where one interval is an ascent and the other a descent, then the Möbius function \(\mu[1,\pi]\) of the interval \([1,\pi]\) is zero. As a consequence, we show that the proportion of permutations of length \(n\) with principal Möbius function equal to zero is asymptotically bounded below by \((1-1/e)^2\ge 0.3995\). This is the first result determining the value of \(\mu[1,\pi]\) for an asymptotically positive proportion of permutations \(\pi\).

We also show that if a permutation \(\phi\) can be expressed as a direct sum of the form \(\alpha\oplus 1 \oplus\beta\), then any permutation \(\pi\) containing an interval order-isomorphic to \(\phi\) has \(\mu[1,\pi]=0\); we deduce this from a more general result showing that \(\mu[\sigma,\pi]=0\) whenever \(\pi\) contains an interval of a certain form. Finally, we show that if a permutation \(\pi\) contains intervals isomorphic to certain pairs of permutations, or to certain permutations of length six, then \(\mu[1,\pi]=0\).@article{bjkm:mobius-zeros, AUTHOR = {Brignall, R. and Jel'inek, V. and Kyn\v{c}l, J. and Marchant, D.}, TITLE = {Zeros of the M\"obius function of permutations}, NOTE = {Submitted}, }

- Bevan, D., Brignall, R., Elvey Price, A., and Pantone, J., A structural characterisation of Av(1324) and new bounds on its growth rate.

[PDF] [BibTeX] [Abstract]We establish an improved lower bound of 10.271 for the exponential growth rate of the class of permutations avoiding the pattern 1324, and an improved upper bound of 13.5. These results depend on a new exact structural characterisation of 1324-avoiders as a subclass of an infinite staircase grid class, together with precise asymptotics of a small "domino" subclass whose enumeration is related to West-two-stack-sortable permutations and planar maps. The bounds are established by carefully combining copies of the dominoes in particular ways consistent with the structural characterisation. The lower bound depends on concentration results concerning the substructure of a typical domino, the determination of exactly when dominoes can be combined in the fewest distinct ways, and technical analysis of the resulting generating function.@unpublished{1324, author = {David Bevan and Robert Brignall and Andrew Elvey Price and Jay Pantone}, title = {A structural characterisation of Av(1324) and new bounds on its growth rate}, note = {Submitted}, }

- Atminas, A., and Brignall, R., Well-quasi-ordering and finite distinguishing number.

[PDF] [BibTeX] [Abstract]Balogh, Bollobás and Weinreich showed that a parameter that has since been termed the*distinguishing number*can be used to identify a jump in the possible speeds of hereditary classes of graphs at the sequence of Bell numbers.

We prove that every hereditary class that lies above the Bell numbers and has finite distinguishing number contains a boundary class for well-quasi-ordering. This means that any such hereditary class which in addition is defined by finitely many minimal forbidden induced subgraphs must contain an infinite antichain. As all hereditary classes below the Bell numbers are well-quasi-ordered, our results complete the answer to the question of well-quasi-ordering for hereditary classes with finite distinguishing number.

We also show that the decision procedure of Atminas, Collins, Foniok and Lozin to decide the Bell number (and which now also decides well-quasi-ordering for classes of finite distinguishing number) has run time bounded by a function of the order of the largest minimal forbidden induced subgraph of the class.@unpublished{ab:wqo-distnumber, AUTHOR = {Atminas, A. and Brignall, R.}, TITLE = {Well-quasi-ordering and finite distinguishing number} NOTE = {Submitted} }

- Atminas, A., Brignall, R., Lozin, V., and Stacho, J., Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs.

[PDF] [BibTeX] [Abstract]We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of these classes is characterised by a finite list of minimal forbidden induced subgraphs. These, therefore, disprove a conjecture due to Daligault, Rao and Thomassé from 2010 claiming that all such minimal classes must be defined by infinitely many forbidden induced subgraphs.

In the same paper, Daligault, Rao and Thomassé make another conjecture that every hereditary class of unbounded clique-width must contain a labelled infinite antichain. We show that the two example classes we consider here satisfy this conjecture. Indeed, they each contain a canonical labelled infinite antichain, which leads us to propose a stronger conjecture: that every hereditary class of graphs that is minimal of unbounded clique-width contains a*canonical*labelled infinite antichain.@unpublished{abls:bichain-min:, Author = { Atminas, A. and Brignall, R. and Lozin, V. and Stacho, J.}, Title = { Minimal Classes of Graphs of Unbounded Clique-width defined by finitely many forbidden induced subgraphs} Note = {Submitted} }

#### Refereed Publications

- Brignall, R., Choi, H., Jeong, J., and Oum, S.-i., Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs.
*Discrete Applied Mathematics*, to appear.

[PDF] [Journal] [BibTeX] [Abstract]A*homogeneous set*of a graph \(G\) is a set \(X\) of vertices such that \(2\le \lvert X\rvert <\lvert V(G)\rvert\) and no vertex in \(V(G)-X\) has both a neighbor and a non-neighbor in \(X\). A graph is*prime*if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs.@unpublished{bcjo:deciding-prime, AUTHOR = {Brignall, R. and Choi, H. and Jeong, J. and Oum, S.-i.}, TITLE = {Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs} NOTE = {To appear in \emph{Discrete Applied Mathematics}} }

- Albert, M.H., Brignall, R., Ruškuc, N., and Vatter, V., Rationality for subclasses of 321-avoiding permutations.
*European Journal of Combinatorics*,**78**(2019), 44-72.

[PDF] [Journal] [BibTeX] [Abstract]We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.@ARTICLE{abrv:av321, author = {Michael Albert and Robert Brignall and Nik Ru\v{s}kuc and Vincent Vatter}, title = {Rationality for subclasses of 321-avoiding permutations}, journal = {European Journal of Combinatorics}, year = {2019}, volume = {78}, pages = {44--72}, doi = {https://doi.org/10.1016/j.ejc.2019.01.001}, issn = {0195-6698}, url = {http://www.sciencedirect.com/science/article/pii/S0195669819300010} }

- Brignall, R., Engen, M., and Vatter, V., A counterexample regarding labelled-well-quasi-ordering.
*Graphs and Combinatorics*,**34 (6)**(2018), 1395-1409.

[PDF] [Journal] [BibTeX] [Abstract]Korpelainen, Lozin, and Razgon conjectured that a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by only finitely many minimal forbidden induced subgraphs is labelled well-quasi-ordered, a notion stronger than that of*n*-well-quasi-order introduced by Pouzet in the 1970s. We present a counterexample to this conjecture. In fact, we exhibit a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by finitely many minimal forbidden induced subgraphs yet is not 2-well-quasi-ordered. This counterexample is based on the widdershins spiral, which has received some study in the area of permutation patterns.@ARTICLE{bev:lwqo, author = {Brignall, Robert and Engen, Michael and Vatter, Vincent}, title = {A Counterexample Regarding Labelled Well-Quasi-Ordering}, journal = {Graphs and Combinatorics}, year = {2018}, volume = {34}, pages = {1395--1409}, number = {6}, month = {Nov}, day = {01}, doi = {10.1007/s00373-018-1962-0}, issn = {1435-5914}, url = {https://doi.org/10.1007/s00373-018-1962-0} }

- Brignall, R., and Marchant, D., The Möbius function of permutations with an indecomposable lower bound.
*Discrete Mathematics*,**341(5)**(2018), 1380-1391.

[PDF] [Journal] [BibTeX] [Abstract]We show that the Möbius function of an interval in a permutation poset where the lower bound is sum (resp. skew) indecomposable depends solely on the sum (resp. skew) indecomposable permutations contained in the upper bound, and that this can simplify the calculation of the Möbius sum. For increasing oscillations, we give a recursion for the Möbius sum which only involves evaluating simple inequalities.@article{bm:mobius, AUTHOR = {Brignall, R. and Marchant, D.}, TITLE = {The M\"obius function of permutations with an indecomposable lower bound}, JOURNAL = {Discrete Math.}, VOLUME = {341}, YEAR = {2018}, PAGES = {1380--1391} }

- Albert, M.H., Atminas, A., and Brignall, R., Characterising inflations of monotone grid classes of permutations.
*Journal of Combinatorial Theory, Series A*,**154**(2018), 444-463.

[PDF] [Journal] [BibTeX] [Abstract]We characterise those permutation classes whose simple permutations are monotone griddable. This characterisation is obtained by identifying a set of nine substructures, at least one of which must occur in any simple permutation containing a long sum of 21s.@article{aab:simple-21s, AUTHOR = {Albert, M.H. and Atminas, A. and Brignall, R.}, TITLE = {Characterising inflations of monotone grid classes of permutations} JOURNAL = {J. Combin. Theory Ser. A}, FJOURNAL = {Journal of Combinatorial Theory, Series A}, VOLUME = {154}, YEAR = {2018}, PAGES = {444--463}, }

- Brignall, R., and Sliačan, J., Juxtaposing Catalan permutation classes with monotone ones.
*Electronic Journal of Combinatorics*,**24(2)**(2017), #P2.11 (16pp)

[PDF] [Journal] [BibTeX] [Abstract]This paper enumerates all juxtaposition classes of the form "Av(*abc*) next to Av(*xy*)", where*abc*is a permutation of length three and*xy*is a permutation of length two. We use Dyck paths decorated by sequences of points to represent elements from such a juxtaposition class. Context free grammars are then used to enumerate these decorated Dyck paths.@article{bs:juxt-catalan, AUTHOR = {Brignall, R. and Slia\v{c}an, J.}, TITLE = {Juxtaposing Catalan permutation classes with monotone ones} JOURNAL = {Electron. J. Combin.}, FJOURNAL = {Electronic Journal of Combinatorics}, VOLUME = {24(2)}, YEAR = {2017}, NUMBER = {2}, PAGES = {P2.11, 16 pp. (electronic)}, }

- Brignall, R., Korpelainen, N., and Vatter, V., Linear clique-width for hereditary classes of cographs.
*Journal of Graph Theory*,**84**(2017), 501-511.

[PDF] [Journal] [BibTeX] [Abstract]The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.@article{bkv:lcw-cographs:, author = {Brignall, R. and Korpelainen, N. and Vatter, V.}, title = {Linear clique-width for hereditary classes of cographs}, journal = {Journal of Graph Theory}, volume = {84}, number = {4}, url = {http://dx.doi.org/10.1002/jgt.22037}, doi = {10.1002/jgt.22037}, pages = {501--511}, year = {2017}, }

- Albert, M.H., and Brignall, R., \(2\times 2\) monotone grid classes are finitely based.
*Discrete Mathematics and Theoretical Computer Science*,**18(2)**, 2016, #1 (Permutation Patterns 2015)

[PDF] [Journal] [BibTeX] [Abstract]In this note, we prove that all \(2 \times 2\) monotone grid classes are finitely based, i.e., defined by a finite collection of minimal forbidden permutations. This follows from a slightly more general result about certain \(2 \times 2\) having two monotone cells in the same row.@article{ab:grid-basis, TITLE = {$2\times 2$ monotone grid classes are finitely based}, AUTHOR = {Albert, Michael and Brignall, Robert}, URL = {http://dmtcs.episciences.org/1378}, JOURNAL = {Discrete Mathematics \& Theoretical Computer Science}, VOLUME = {vol. 18 no. 2, Permutation Patterns 2015}, PAGES = {\#1}, YEAR = {2016}, MONTH = Nov, KEYWORDS = {Mathematics - Combinatorics ; 05A05}, }

- Brignall, R., Lozin, V., and Stacho, J., Bichain graphs: geometric model and universal graphs.
*Discrete Applied Mathematics*,**199**(2016), 16-29

[PDF] [Journal] [BibTeX] [Abstract]Bichain graphs form a bipartite analog of split permutation graphs, also known as split graphs of Dilworth number 2. Unlike graphs of Dilworth number 1 that enjoy many nice properties, split permutation graphs are substantially more complex. To better understand the global structure of split permutation graphs, in the present paper we study their bipartite analog. We show that bichain graphs admit a simple geometric representation and have a universal element of quadratic order, i.e. a bichain graph with \(n^2\) vertices that contains all \(n\)-vertex bichain graphs as induced subgraphs. The latter result improves a recent cubic construction of universal split permutation graphs.@article{bls:bichain:, author = {Brignall, R. and Lozin, V and Stacho, J.}, title = {Bichain graphs: geometric model and universal graphs}, journal = {Discrete Appl. Math.}, year = {2016}, volume = {199}, pages = {16--29} }

- Atminas, A., Brignall, R., Korpelainen, N., Lozin, V., and Vatter, V., Well-quasi-order for permutation graphs omitting a path and a clique.
*Electronic Journal of Combinatorics***22(2)**(2015), #P2.20 (21pp)

[PDF] [Journal] [BibTeX] [Abstract]We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting \(P_5\) and a clique of any size is well-quasi-ordered. This is proved by giving a structural decomposition of the corresponding permutations. We also exhibit three infinite antichains to show that the classes of permutation graphs omitting \(\{P_6,K_6\}\), \(\{P_7,K_5\}\), and \(\{P_8,K_4\}\) are not well-quasi-ordered.@article{ablkv:wqo-path-clique:, AUTHOR = { Atminas, A. and Brignall, R. and Korpelainen, N. and Lozin, V. and Vatter, V.}, TITLE = { Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique}, JOURNAL = {Electron. J. Combin.}, FJOURNAL = {Electronic Journal of Combinatorics}, VOLUME = {22(2)}, YEAR = {2015}, NUMBER = {2}, PAGES = {P2.20, 21 pp. (electronic)}, }

- Brignall, R., and Vatter, V., A simple proof of a theorem of Schmerl and Trotter for permutations.
*Journal of Combinatorics*,**6**(2015) No. 1-2, 47-54

[PDF] [Journal] [BibTeX] [Abstract]When specialized to the context of permutations, Schmerl and Trotter's Theorem states that every simple permutation which is not a parallel alternation contains a simple permutation with one fewer entry. We give an elementary proof of this result.@article{bv:schmerl-trotter:, AUTHOR = { Brignall, R. and Vatter, V.}, TITLE = { A simple proof of a theorem of Schmerl and Trotter for permutations} JOURNAL = {J. Combin.}, FJOURNAL = {Journal of Combinatorics}, VOLUME = {6}, YEAR = {2015}, NUMBER = {1--2}, PAGES = {47--54}, }

- Albert, M.H., and Brignall, R., Enumerating indices of Schubert varieties defined by inclusions.
*Journal of Combinatorial Theory, Series A*,**123**(2014), 154-168

[PDF] [Journal] [BibTeX] [Abstract]By extending the notion of grid classes to include infinite grids, we establish a structural characterisation of the simple permutations in Av(4231, 31524, 42513, 351624), a pattern class which has three different connections with algebraic geometry, including the specification of indices of Schubert varieties defined by inclusions. This characterisation leads to the enumeration of the class.@article{ab:enumerating-indices:, AUTHOR = {Albert, A. and Brignall, R.}, TITLE = {Enumerating indices of Schubert varieties defined by inclusions} JOURNAL = {J. Combin. Theory Ser. A}, FJOURNAL = {Journal of Combinatorial Theory, Series A}, VOLUME = {123}, YEAR = {2014}, NUMBER = {1--2}, PAGES = {154--168}, }

- Albert, M.H., Brignall, R., and Vatter, V., Large infinite antichains of permutations.
*Pure Mathematics and Applications*,**24**(2013) No. 2, 47-57

[PDF] [Journal] [BibTeX] [Abstract]Infinite antichains of permutations have long been used to construct interesting permutation classes and counterexamples. We prove the existence and detail the construction of infinite antichains with arbitrarily large growth rates. As a consequence, we show that every proper permutation class is contained in a class with a rational generating function. While this result implies the conclusion of the Marcus-Tardos theorem, that theorem is used in our proof.@article {antichains-large, AUTHOR = {Albert, Michael H. and Brignall, Robert and Vatter, Vincent}, TITLE = {Large infinite antichains of permutations}, JOURNAL = {Pure Math. Appl. (PU.M.A.)}, VOLUME = {24}, YEAR = {2013}, NUMBER = {2}, PAGES = {47--57}, ISSN = {1218-4586}, }

- Brignall, R., Georgiou, N., and Waters, R., Modular decomposition and the reconstruction conjecture.
*Journal of Combinatorics*,**3**(2012), 123-134

[PDF] [Journal] [BibTeX] [Abstract]We prove that a large family of graphs which are decomposable with respect to the modular decomposition can be reconstructed from their collection of vertex-deleted subgraphs.@article {bgw:recon, AUTHOR = {Brignall, Robert and Georgiou, Nicholas and Waters, Robert J.}, TITLE = {Modular decomposition and the reconstruction conjecture}, JOURNAL = {J. Comb.}, VOLUME = {3}, YEAR = {2012}, NUMBER = {1}, PAGES = {123--134}, ISSN = {2156-3527}, URL = {http://dx.doi.org/10.4310/JOC.2012.v3.n1.a6}, }

- Albert, M.H., Atkinson, M.D., and Brignall, R., The enumeration of three pattern classes using monotone grid classes.
*Electronic Journal of Combinatorics***19(3)**(2012), #P20 (34pp)

[PDF] [Journal] [BibTeX] [Abstract]The structure of three pattern classes Av(2143, 4321), Av(2143, 4312) and Av(1324, 4312) is determined using the machinery of monotone grid classes. This allows the permutations in these classes to be described in terms of simple diagrams and regular languages and, using this, the rational generating functions which enumerate these classes are determined.@article{aab:three-enumerations:, Author = {Albert, M. H. and Atkinson, M. D. and Brignall, R.}, Title = {The enumeration of three pattern classes using monotone grid classes}, JOURNAL = {Electron. J. Combin.}, FJOURNAL = {Electronic Journal of Combinatorics}, VOLUME = {19(3)}, YEAR = {2012}, NUMBER = {3}, PAGES = {P20, 34 pp. (electronic)}, }

- Brignall, R., Grid classes and partial well order.
*Journal of Combinatorial Theory Series A*,**119**(2012), 99-116

[PDF] [Journal] [BibTeX] [Abstract]We prove necessary and sufficient conditions on a family of (generalised) gridding matrices to determine when the corresponding permutation classes are partially well-ordered. One direction requires an application of Higman's Theorem and relies on there being only finitely many simple permutations in the only non-monotone cell of each component of the matrix. The other direction is proved by a more general result that allows the construction of infinite antichains in any grid class of a matrix whose graph has a component containing two or more non-monotone-griddable cells. The construction uses a generalisation of pin sequences to grid classes, together with a number of symmetry operations on the rows and columns of a gridding.@article{brignall:pwo-grid-classes:, author = {Brignall, R.}, title = {Grid classes and partial well order}, journal = {J. Combin. Theory Ser. A}, year = {2012}, volume = {119}, pages = {99--116}, number = {1}, fjournal = {Journal of Combinatorial Theory. Series A}, }

- Albert, M.H., Atkinson, M.D., and Brignall, R., The enumeration of permutations avoiding 2143 and 4231.
*Pure Mathematics and Applications*,**22**(2011) No. 2, 87-98

[PDF] [Journal] [BibTeX] [Abstract]We enumerate the pattern class Av(2143, 4231) and completely describe its permutations. The main tools are simple permutations and monotone grid classes.@article{aab:2143-4231-enum:, Author = {Albert, M. H. and Atkinson, M. D. and Brignall, R.}, Title = {The enumeration of permutations avoiding 2143 and 4231}, JOURNAL = {Pure Math. Appl. (PU.M.A.)}, FJOURNAL = {Pure Mathematics and Applications. PU.M.A.}, VOLUME = {22}, YEAR = {2011}, NUMBER = {2}, PAGES = {87--98}, }

- Brignall, R., Ruškuc, N., and Vatter, V., Simple extensions of combinatorial structures.
*Mathematika*,**57**(2011), 193-214

[PDF] [Journal] [BibTeX] [Abstract]An interval in a combinatorial structure \(R\) is a set \(I\) of points which are related to every point in \(R\setminus I\) in the same way. A structure is simple if it has no proper intervals. Every combinatorial structure can be expressed as an inflation of a simple structure by structures of smaller sizes --- this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: An arbitrary structure \(S\) of size $n\) belonging to a class \(\mathcal{C}\) can be embedded into a simple structure from \(\mathcal{C}\) by adding at most \(f(n)\) elements. We prove such results when \(\mathcal{C}\) is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than 2. The function \(f(n)\) in these cases is 2, \(\lceil \log_2(n+1)\rceil\), \(\lceil (n+1)/2\rceil\), \(\lceil (n+1)/2\rceil\), \(\lceil \log_4(n+1)\rceil\), \(\lceil \log_3(n+1)\rceil\) and 1, respectively. In each case these bounds are best possible.@article {simple-extensions, AUTHOR = {Brignall, Robert and Ru{\v{s}}kuc, Nik and Vatter, Vincent}, TITLE = {Simple extensions of combinatorial structures}, JOURNAL = {Mathematika}, VOLUME = {57}, YEAR = {2011}, NUMBER = {2}, PAGES = {193--214}, ISSN = {0025-5793}, URL = {http://dx.doi.org/10.1112/S0025579310001518}, }

- Albert, M.H., Atkinson, M.D., Brignall, R., Ruškuc, N., Smith, R., and West, J., Growth rates for subclasses of Av(321).
*Electronic Journal of Combinatorics***17(1)**(2010), #R141 (16pp)

[PDF] [Journal] [BibTeX] [Abstract]Pattern classes which avoid 321 and other patterns are shown to have the same growth rates as similar (but strictly larger) classes obtained by adding articulation points to any or all of the other patterns. The method of proof is to show that the elements of the latter classes can be represented as*bounded merges*of elements of the original class, and that the bounded merge construction does not change growth rates.@article {albert:321avoiders, AUTHOR = {Albert, M. H. and Atkinson, M. D. and Brignall, R. and Ru\v{s}kuc, N. and Smith, Rebecca and West, J.}, TITLE = {Growth rates for subclasses of Av(321)}, JOURNAL = {Electron. J. Combin.}, FJOURNAL = {Electronic Journal of Combinatorics}, VOLUME = {17(1)}, YEAR = {2010}, NUMBER = {1}, PAGES = {Research Paper 141, 16 pp. (electronic)}, }

- Brignall, R., A survey of simple permutations. S. Linton, N. Ruškuc and V. Vatter, Eds., vol. 376 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 41-65

[PDF] [Book] [BibTeX] [Abstract]We survey the known results about simple permutations. In particular, we present a number of recent enumerative and structural results pertaining to simple permutations, and show how simple permutations play an important role in the study of permutation classes. We demonstrate how classes containing only finitely many simple permutations satisfy a number of special properties relating to enumeration, partial well-order and the property of being finitely based.@incollection {brignall:a-survey-of-sim:, AUTHOR = {Brignall, Robert}, TITLE = {A Survey of Simple Permutations}, BOOKTITLE = {Permutation Patterns}, SERIES = {London Math. Soc. Lecture Note Ser.}, VOLUME = {376}, PAGES = {41-65}, PUBLISHER = {Cambridge Univ. Press}, ADDRESS = {Cambridge}, YEAR = {2010}, EDITOR = {Linton, Steve and Ru\v{s}kuc, Nik and Vatter, Vincent} }

- Brignall, R., Ekhad, S.B., Smith, R., and Vatter, V., Almost avoiding permutations.
*Discrete Mathematics***309**(2009), 6626-6631

[PDF] [Journal] [BibTeX] [Abstract]We investigate a new notion of approximately avoiding a permutation: \(\pi\)*almost avoids*\(\beta\) if one can remove a single entry from \(\pi\) to obtain a \(\beta\)-avoiding permutation.@article{brignall:almost, AUTHOR = {Brignall, Robert, and Ekhad, Shalosh B., and Smith, Rebecca and Vatter, Vincent}, TITLE = {Almost avoiding permutations} JOURNAL = {Discrete Math.}, VOLUME = {309}, YEAR = {2009}, PAGES = {6626--6631}, }

- Brignall, R., Huczynska, S., and Vatter, V., Decomposing simple permutations, with enumerative consequences.
*Combinatorica*,**28**(4) (2008) 385-400

[PDF] [Journal] [BibTeX] [Abstract]We prove that every sufficiently long simple permutation contains two long almost disjoint simple subsequences, and then we show how this result has enumerative consequences. For example, it implies that, for any \(r\), the number of permutations with at most \(r\) copies of 132 has an algebraic generating function (this was previously proved, constructively, by Bóna and (independently) Mansour and Vainshtein).@article {brignall:simple-decomp:, AUTHOR = {Brignall, Robert and Huczynska, Sophie and Vatter, Vincent}, TITLE = {Decomposing simple permutations, with enumerative consequences}, JOURNAL = {Combinatorica}, VOLUME = {28}, YEAR = {2008}, NUMBER = {4}, PAGES = {385--400}, ISSN = {0209-9683}, }

- Brignall, R., Huczynska, S., and Vatter, V., Simple permutations and algebraic generating functions.
*Journal of Combinatorial Theory Series A***115**(2008), 423-441

[PDF] [Journal] [BibTeX] [Abstract]A simple permutation is one that never maps a nontrivial contiguous set of indices contiguously. Given a set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, we provide a framework for enumerating subsets that are restricted by properties belonging to a finite "query-complete set". Such properties include being even, being an alternating permutation, and avoiding a given generalised (blocked or barred) pattern. We show that the generating functions for these subsets are always algebraic, thereby generalising recent results of Albert and Atkinson. We also apply these techniques to the enumeration of involutions and cyclic closures@article {brignall:simple-enum:, AUTHOR = {Brignall, Robert and Huczynska, Sophie and Vatter, Vincent}, TITLE = {Simple permutations and algebraic generating functions}, JOURNAL = {J. Combin. Theory Ser. A}, VOLUME = {115}, YEAR = {2008}, NUMBER = {3}, PAGES = {423--441}, ISSN = {0097-3165}, }

- Brignall, R., Ruškuc, N., and Vatter, V., Simple permutations: decidability and unavoidable substructures.
*Theoretical Computer Science***391**(2008), 150-163

[PDF] [Journal] [BibTeX] [Abstract]We prove that it is decidable whether a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length \(k\).@article {brignall:simple-decide:, AUTHOR = {Brignall, Robert and Ru{\v{s}}kuc, Nik and Vatter, Vincent}, TITLE = {Simple permutations: decidability and unavoidable substructures}, JOURNAL = {Theoret. Comput. Sci.}, VOLUME = {391}, YEAR = {2008}, NUMBER = {1-2}, PAGES = {150--163}, ISSN = {0304-3975}, }

- Albert, M.H., Atkinson, M.D., and Brignall, R., Permutation classes of polynomial growth.
*Annals of Combinatorics***11**(2007), no. 3-4, 249--264

[PDF] [Journal] [BibTeX] [Abstract]A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterised as those permutations not involving a particular set of forbidden permutations. A simple collection of necessary and sufficient conditions on sets of forbidden permutations which ensure that the associated pattern class is of polynomial growth is determined. A catalogue of all such sets of forbidden permutations having three or fewer elements is provided together with bounds on the degrees of the associated enumerating polynomials.@article {albert:polypaper:, AUTHOR = {Albert, M. H. and Atkinson, M. D. and Brignall, Robert}, TITLE = {Permutation classes of polynomial growth}, JOURNAL = {Ann. Comb.}, FJOURNAL = {Annals of Combinatorics}, VOLUME = {11}, YEAR = {2007}, NUMBER = {3-4}, PAGES = {249--264}, ISSN = {0218-0006}, }

- Brignall, R., Wreath products of permutation classes.
*Electronic Journal of Combinatorics***14**(2007), #R46 (15pp)

[PDF] [Journal] [BibTeX] [Abstract]A permutation class which is closed under pattern involvement may be described in terms of its basis. The wreath product construction \(X \wr Y\) of two permutation classes \(X\) and \(Y\) is also closed, and we investigate classes \(Y\) with the property that, for any finitely based class \(X\), the wreath product \(X \wr Y\) is also finitely based.@article {brignall:wreath-product:, AUTHOR = {Brignall, Robert}, TITLE = {Wreath products of permutation classes}, JOURNAL = {Electron. J. Combin.}, FJOURNAL = {Electronic Journal of Combinatorics}, VOLUME = {14}, YEAR = {2007}, NUMBER = {1}, PAGES = {Research Paper 46, 15 pp. (electronic)}, ISSN = {1077-8926}, }

#### Conference Paper

- Bevan, D., Brignall, R., Elvey Price, A., and Pantone, J., Staircases, dominoes, and the growth rate of 1324-avoiders.
*Electronic Notes in Discrete Mathematics*,**61**(August 2017), 123-129.

[PDF] [Journal] [BibTeX] [Abstract]We establish a lower bound of 10.271 for the growth rate of the permutations avoiding 1324, and an upper bound of 13.5. This is done by first finding the precise growth rate of a subclass whose enumeration is related to West-2-stack-sortable permutations, and then combining copies of this subclass in particular ways.@article{1324endm, author = {David Bevan and Robert Brignall and Andrew Elvey Price and Jay Pantone}, title = {Staircases, dominoes, and the growth rate of 1324-avoiders }, journal = {Electronic Notes in Discrete Mathematics }, year = {2017}, volume = {61}, pages = {123 - 129}, note = {The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 17) }, }

#### Theses

## TALKS

#### Invited Talks

- Permutation Patterns 2018, Dartmouth College, NH, USA, 9th-13th July 2018. [PDF]
- Scottish Combinatorics Meeting, St Andrews, Scotland, 25th April 2017. [PDF]
- Pure Mathematics Colloquium, St Andrews, Scotland, 13th January 2016. [PDF]
- Discrete Math Seminar, KAIST, Daejeon, South Korea, 11th November 2015. [PDF] [Video]
- Combinatorics Seminar, University of Bristol, UK, 27th October 2015. [PDF]
- Combinatorics Seminar, University of Florida, FL, USA, 21st April 2015.
- Combinatorics Workshop, South West and South Wales Regional Meeting of the London Mathematical Society, Plymouth, Thursday 18th December 2014. [PDF]
- Mathematics Seminar, Derby, UK, 9th December 2014. [PDF]
- Combinatorics Seminar, Warwick, UK, 28th November 2014. [PDF]
- Pure Mathematics Seminar, Royal Holloway, UK, 11th March 2014. [PDF]
- Combinatorics Seminar, University of Florida, FL, USA, 20th March 2012.
- Mathematics Seminar, Birkbeck College, UK, 29th February 2012. [PDF]
- Computer Science Seminar, Strathclyde, UK, 3rd February 2012. [PDF]
- DIMAP Seminar, Warwick, UK, 22nd November 2011. [PDF]
- Pure Mathematics Seminar, Royal Holloway, UK, 15th November 2011. [PDF]
- Combinatorics Seminar, University of Bristol, UK, 9th June 2011. [PDF]
- Mathematics Seminar, The Open University, UK, 8th February 2011. [PDF]
- Pure Mathematics Colloquium, St Andrews, Scotland, 13th May 2010. [PDF]
- Combinatorics Seminar, Dartmouth College, NH, USA, 8th February 2010. [PDF]
- DIMAP Seminar, Warwick, UK, 3rd November 2009. [PDF]
- Algebra and Geometry Seminar, Bristol, UK, 13th February 2008 [PDF]

#### Contributed Talks

- Genomics, Pattern Avoidance, and Statistical Mechanics, Schloss Dagstuhl Leibniz-Zentrum für Informatik, Germany, 8th November 2018. [PDF]
- European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17), Vienna, Austria, 28th August 2017. [PDF]
- 15th International Conference on Permutation Patterns, Reykjavik, Iceland, 29th June 2017. [PDF]
- 22nd British Combinatorial Conference, Royal Holloway, UK, 2nd July 2013. [PDF]
- 9th International Conference on Permutation Patterns, California Polytechnic State University, San Luis Obispo, CA, USA, 24th June 2011. [PDF]
- Workshop on Combinatorics and Graph Theory, DIMAP, Warwick, UK, 4th April 2011. [PDF]
- 8th International Conference on Permutation Patterns, Dartmouth College, NH, USA, 10th August 2010. [Notes - 1.2MB]
- From A=B to Z=60, Conference in Honor of Doron Zeilberger's 60th Birthday, Rutgers University, NJ, USA, 28th May 2010. [Abstract] [Video]
- 7th International Conference on Permutation Patterns, Florence, Italy, 15th July 2009. [PDF]
- 22nd British Combinatorial Conference, St Andrews, Scotland, 7th July 2009. [PDF]
- 6th International Conference on Permutation Patterns, Dunedin, New Zealand, 17th June 2008. [PDF]
- 32nd Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, Dunedin, New Zealand, 7th December 2007 [PDF]
- 5th International Conference on Permutation Patterns, St Andrews, Scotland, 13th June 2007. [PDF]
- 18th Postgraduate Combinatorial Conference, St Andrews, Scotland, 6th June 2007. [PDF]
- 4th International Conference on Permutation Patterns, Reykjavik, Iceland, 15th June 2006. [PDF]
- EMS Postgraduate Students' Meeting, The Burn, Edzell, 11th May 2005. [PDF]
- 3rd International Conference on Permutation Patterns, Gainesville, Florida, USA, 10th March 2005. [PDF]

## CONTACT

#### Address

School of Mathematics and Statistics, The Open University, Milton Keynes, MK7 6AA

Before "gmail.com", add "rbrignall"

#### Telephone

+44 (0)1908 3x32744