Almost avoiding permutations
We investigate the notion of almost avoiding a permutation: $π$ almost avoids $β$ if one can remove a single entry from $π$ to obtain a $β$-avoiding permutation.
Source author record
Robert Brignall
Robert Brignall appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
11works
2topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
11 published item(s)
preprint2016arXiv
Linear Clique-Width for Hereditary Classes of Cographs
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.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
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.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
A simple proof of a theorem of Schmerl and Trotter for permutations
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.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Enumerating indices of Schubert varieties defined by inclusions
By extending the notion of grid classes to include infinite grids, we establish a structural characterisation of the simple permutations in Av(4231, 35142, 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.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Large infinite antichains of permutations
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.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Modular Decomposition and the Reconstruction Conjecture
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.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
The enumeration of three pattern classes
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.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Grid classes and partial well order
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.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
The enumeration of permutations avoiding 2143 and 4231
We enumerate the pattern class Av(2143,4231) and completely describe its permutations. The main tools are simple permutations and monotone grid classes.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Simple extensions of combinatorial structures
An interval in a combinatorial structure S is a set I of points which relate to every point from S 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 C can be embedded into a simple structure from C by adding at most f(n) elements. We prove such results when 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.
0 citations0 reviewsNo code linkedOpen access