Queen Mary, University of London
School of Mathematical Sciences
Random strongly graphs having the n-e.c. property
Applications are invited for a PhD studentship. Applicants should have a
good first degree in a subject containing a substantial amount of
probability and combinatorics or an MSc in Mathematics.
The project is on the properties of random structures having the n-e.c.
property. The student will work mainly at Queen Mary, University of
London, under the supervision of Dr. Dudley Stark
(http://www.maths.qmul.ac.uk/~dstark). Professor Peter Cameron will be the
secondary supervisor. Work may involve collaboration with Professor
Anthony Bonato of Wilfrid Laurier University.
A description of the project is given below.
The studentship covers tuition living expenses of approximately £15,000
per annum and tuition fees at the home student rate (non-EU students will
require additional funding of about £.7,000 per annum).
Project Description;
A graph has the n-existentially closed (n-e.c.) property if, for every two
disjoint subsets of vertices A and B whose union contains n vertices,
there exists a vertex outside of the union of A and B adjacent to all of
the vertices in A and adjacent to none of the vertices in B. The n-e.c.
property is of importance in the theory of logical limit laws for random
combinatorial structures.
It is known that most graphs have the n-e.c. property. However it is of
interest to find graphs that are regular in some sense having the n-e.c.
property. A graph is strongly regular if it is regular and, conditional on
whether or not two vertices are adjacent, the number of vertices adjacent
to both is constant. Cameron and Stark used probabilistic methods to prove
the existence of a large class of strongly regular graphs having the
n-e.c. property.
Bonato et. al. used a different, simpler method to show that a different
probabilistic construction produces at least one strongly regular graph
with the n-e.c. property. It is desirable to analyze their method further.
In particular, it would be of interest to show that their method gives
many strongly regular graphs and to generalize their method to give
strongly regular graphs having new parameters.
Further research might include finding generalized methods using designs
and finite geometries. Other properties of random strongly regular graphs,
such as the distribution of small cycles, might be investigated.
This project is on the boundary between probability and combinatorics. The
School of Mathematical Sciences at Queen Mary has an international
reputation for research in both of these areas, with active research in
probabilistic combinatorics and design theory. The primary supervisor
works mainly in the first area and is particularly interested in random
graphs and random combinatorial structures. The secondary supervisor works
in design theory. Queen Mary has a weekly, well-attended combinatorics
workshop.
--
Professor Steven G Gilmour
School of Mathematical Sciences
Queen Mary, University of London
Mile End Road
London E1 4NS
United Kingdom
Tel: +44 (0)20 7882 7833
Fax: +44 (0)20 8981 9587 (department fax, not private)
Web page: http://www.maths.qmul.ac.uk/~sgg
