
New Directions in Combinatorics
(9  27 May 2016)
~ Abstracts ~
Isoperimetric problems in association schemes Sebastian Cioaba, University of Delaware, USA
What is the minimum number of vertices/edges whose removal disconnects a connected graph into components of size at least k? What is the minimum size of the vertex or edgeneighborhood of a subset of k vertices of a graph? In this talk, I will describe what I know about these questions for graphs in association schemes and present some open problems.
« Back... A linear algebraic approach to partial difference sets in Abelian groups Stefaan De Winter, Michigan Technological University, USA
The classical tool for studying partial difference sets has been the use of characters and computations in the group ring. Many interesting necessary conditions for existence have been obtained this way, but at the same time the existence question for partial difference sets remains open for many parameter sets. In this talk I will explain how recently the use of linear algebra has led to a new multiplier theorem for partial dierence sets in Abelian groups, and describe how this has led to new nonexistence and classification results for these partial difference sets.
« Back... Permutations and number theory Ben Green, University of Oxford, UK
I will discuss two recent joint theorems about permutations with S. Eberhard and K. Ford. Let S_n denote the symmetric group on n letters, that is to say the group consisting of all permutations on n letters. Theorem 1: let k be fixed. Pick pi in S_n at random, where n is large. What is the probability that pi fixes some set of size k? Theorem 2: Pick pi_1,...,pi_m in S_n at random. For which m is it almost surely true that, however you conjugate these permutations to pi'_1,.,,,.pi'_m, the resulting permutations generate S_n?
It turns out that there is a close analogy between the cycle decomposition of random permutations and the prime factorisations of random integers, and this analogy helped us prove the theorems just mentioned. I will describe it in my talk.
« Back... Finite field models in additive combinatorics Ben Green, University of Oxford, UK
We will look at some of the basic techniques and results of additive combinatorics in the setting of vector spaces over finite fields. Topics will include most of the following.
1. The Fourier transform. Proof of Meshulam's upper bound for subsets of F_3^n free of 3term progressions (arcs)
2. Sumset estimates and Freiman's theorem over finite fields.
3. The BalogSzemerediGowers theorem.
4. Upper bounds for subsets of F_p^n free of 4term progressions (sketch
« Back... Switched strongly regular graphs from finite projective spaces Alice, Man Wa Hui, University of KwaZuluNatal, South Africa
Godsil and McKay (1982) introduced a method to generate cospectral graph by preforming some switch. In case when the graph is a strongly regular graph, the switched graph has a same spectrum as the original and thus is also a strongly regular graph with the same parameters. Thus, GodsilMcKay switching provides a tool to construct new strongly regular graph from known ones. In this talk, recent results on repeated GodsilMcKay switching on three families of strongly regular graphs constructed from a nonsingular quadric in ndimensional projective space PG(n; 2) over F2 will be presented.
Keywords: strongly regular graph, projective geometry, GodsilMcKay switching, symplectic graph
« Back... Existence and enumeration of designs Peter Keevash, University of Oxford, UK
A Steiner Triple System on a set X is a collection T of 3element subsets of X such that every pair of elements of X is contained in exactly one of the triples in T. An example considered by Plücker in 1835 is the affine plane of order three, which consists of 12 triples on a set of 9 points. Plücker observed that a necessary condition for the existence of a Steiner Triple System on a set with n elements is that n be congruent to 1 or 3 mod 6. In 1846, Kirkman showed that this necessary condition is also sufficient. In 1974, Wilson conjectured an approximate formula for the number of such systems. We will outline a proof of this conjecture, and a more general estimate for the number of Steiner systems. Our main tool is the technique of Randomised Algebraic Construction, which we introduced to resolve a question of Steiner from 1853 on the existence of designs.
« Back... Quadratic residues and difference sets Vsevolod Lev, The University of Haifa at Oranim, Israel
It has been conjectured by Sarkozy that with finitely many exceptions, the set of quadratic residues modulo a prime p cannot be represented as a sumset { a+b \colon a\in A, b\in B } with nonsingleton A, B \subset F_p. The case A=B of this conjecture has been established by Shkredov. The analogous problem for differences remains open: is it true that for all sufficiently large primes p, the set of quadratic residues modulo p is not of the form { ab \colon a,b \in A, a \ne b } with A \subset F_p?
We present the results of our recent paper, join with Jack Sonn, where a presumably more tractable variant of this problem is considered: is there a set A \subset F_p such that every quadratic residue has a *unique* representation as ab with a,b\in A, and no nonresidue is representable in this form? We give a number of necessary conditions for the existence of such A, involving for the most part the behavior of primes dividing p1. These conditions enabled us to rule out all primes p in the range 13 < p < 10^{20}.
« Back...

