# Extremal Combinatorics on Permutations

• Applications accepted all year round
• Competition Funded PhD Project (Students Worldwide)

## Project Description

The School of Mathematical Sciences of Queen Mary University of London invite applications for a PhD project commencing either in September 2020 for students seeking funding, or in January 2020 or April 2020 for self-funded students. The deadline for funded applications is the 31st of January 2020. The deadline for China Scholarship Council Scheme applications is 12th January 2020.

This project will be supervised by Dr. Robert Johnson.

Many classical problems in extremal set theory have interesting and under-explored analogues in the setting of permutations. For example, a family of sets is t-intersecting if any two sets in the family intersect in at least t elements. By analogy a family of permutations is t-intersecting if they pointwise agree (thought of as bijections on some fixed ground set) in at least t places. An old result of Erdos, Ko and Rado shows that if n is much larger than t, the largest t-intersecting family of subsets of an n-set has size equal to the family of all sets containing a fixed t-set. The corresponding result for permutations, that for n much larger than t, the largest t-intersecting family of permutations of an n-set has size equal to the family of all permutations fixing (pointwise) a given t-set, was only proved in 2011 by Ellis, Friedgut and Pilpel [EFP] using techniques from algebraic combinatorics and representation theory. There are other ways to transfer the notion of intersection to permutations for which much less is known. For example, what is the largest family of permutations of an n-set for which any two of them agree in the relative order they give to a t-set of elements?

A natural way to think of many set theoretic problems is via the structure of the discrete hypercube (this graph is the covering relation of the partial order on subsets of an n-element set given by containment). For permutations there are two analogues of this: the weak and strong Bruhat order on the symmetric group. The Harris-Kleitman inequality (and its many extensions) establishes correlation results on events satisfying the property of being closed upwards in the containment order (we will call these \emph{up-sets}). In its simplest form it states that it we pick a uniformly random subset then any two up-set events are positively correlated. In the permutation setting, we have two notions of up-set coming from the strong and weak orders. It is known [JLL] that these show different correlation behaviour. However, these results leave many questions unanswered. For instance there are many natural (non-uniform) measures on permutations for which correlation properties of up-sets are not understood.

As these examples suggests, many set theory problems can be translated into the realm of permutations and the resulting questions are often interesting and may need new techniques. These problems are often quite different from the kind of questions arising from the more common algebraic view of permutations, and as such they make a nice counterpoint to the existing body of work on permutations. There are numerous possible directions that a PhD project in this area could take. The exact direction would depend on the background and interests of the candidate.

The application procedure is described on the School website. For further inquiries please contact Dr Robert Johnson at . This project is eligible for full funding, including support for 3.5 years’ study, additional funds for conference and research visits and funding for relevant IT needs. Applicants interested in the full funding will have to participate in a highly competitive selection process.

## Funding Notes

This project is eligible for full funding, including support for 3.5 years’ study, additional funds for conference and research visits and funding for relevant IT needs.

This project can be undertaken as a self-funded project. Self-funded applications are accepted year-round for a January, April or September start.

We welcome applicants through the China Scholarship Council Scheme (deadline for applications 12th January 2020).

The School of Mathematical Sciences is committed to the equality of opportunities and to advancing women’s careers. As holders of a Bronze Athena SWAN award we offer family friendly benefits and support part-time study.

## References

[EFP] D. Ellis, E. Friedgut, H. Pilpel, Intersecting families of permutations, (2011), Journal of the American Mathematical Society 24 649--682.

[JLL] J.R. Johnson, I. Leader and E. Long (2019) Correlation for permutations}, preprint: https://arxiv.org/abs/1909.03770

## How good is research at Queen Mary University of London in Mathematical Sciences?

FTE Category A staff submitted: 34.80

Research output data provided by the Research Excellence Framework (REF)

## Email Now

Insert previous message below for editing?
You haven’t included a message. Providing a specific message means universities will take your enquiry more seriously and helps them provide the information you need.
Why not add a message here
* required field
Send a copy to me for my own records.