|
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 edge-neighborhood 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 di erence sets in Abelian groups, and describe how this has led to new non-existence 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 3-term progressions (arcs)
2. Sumset estimates and Freiman's theorem over finite fields.
3. The Balog-Szemeredi-Gowers theorem.
4. Upper bounds for subsets of F_p^n free of 4-term progressions (sketch
« Back... Switched strongly regular graphs from finite projective spaces
Alice, Man Wa Hui, University of KwaZulu-Natal, 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, Godsil-McKay switching provides a tool to construct new strongly regular graph from known ones. In this talk, recent results on repeated Godsil-McKay switching on three families of strongly regular graphs constructed from a non-singular quadric in n-dimensional projective space PG(n; 2) over F2 will be presented.
Keywords: strongly regular graph, projective geometry, Godsil-McKay 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 3-element 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 non-singleton 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 { a-b \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 a-b with a,b\in A, and no non-residue 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 p-1. These conditions enabled us to rule out all primes p in the range 13 < p < 10^{20}.
« Back...
|
|