Royal Holloway

Last summer, there was a lot of activity regarding an old conjecture of van der Waerden, culminating in its solution by Bhargava, and including joint work by Sam Chow and myself on which I want to report in this talk: We showed that the number of irreducible monic integer polynomials of degree n, with coefficients in absolute value bounded by H, which have Galois group different from S_n and A_n, is of order of magnitude O(H^{n-1.017}), providing that n is at least 3 and is different from 7,8,10. Apart from the alternating group and excluding degrees 7,8,10, this establishes the aforementioned conjecture to the effect that irreducible non-S_n polynomials are significantly less frequent than reducible polynomials.

Soluble groups, and other classes of groups that can be built from simpler groups, are useful test cases for studying group properties. I will talk about techniques for building profinite groups from simpler ones, and how  to use these to investigate the cohomology of such groups and recover information about the group structure.

Let G be a permutation group acting on a set Omega. For g in G, let pi(g) denote the partition of Omega given by the orbits of g. The set of all partitions of Omega is naturally ordered by refinement and admits lattice operations of meet and join. My talk concerns the groups G such that the partitions pi(g) for g in G form a sublattice. This condition is highly restrictive, but there are still many interesting examples. These include centralisers in the symmetric group Sym(Omega) and a class of profinite abelian groups which act on each of their orbits as a subgroup of the Prüfer group. I will also describe a classification of the primitive permutation groups of finite degree whose set of orbit partitions is closed under taking joins, but not necessarily meets.

This talk is on joint work with John R. Britnell (Imperial College).

In the Max Acyclic Subdigraph problem we are given a digraph $D$ and ask whether $D$ contains an acyclic subdigraph with at least $k$ arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time $f(k)n$ for solving the problem, where $f$ is a computable function of $k$ only and $n=|V(D)|$. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of $D$ is $m/2$, where $m$ is the number of arcs in $D$. Thus, it is natural to ask another question: does $D$ have an acyclic subdigraph with at least $m/2 +k$ arcs?

Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max $r$-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable.

Methods involved in proving these results include probabilistic inequalities, harmonic analysis of real-valued

functions with boolean domain, linear algebra, and algorithmic-combinatorial arguments. Some new results obtained in this research are of potential interest for several areas of discrete mathematics and computer science. The examples include a new variant of the hypercontractive inequality and an association of Fourier expansions of real-valued functions with boolean domain with weighted systems of linear equations over $F^n_2$.

I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo.

In a joint project with Christopher Voll, I have investigated the representation zeta functions of compact p-adic Lie groups. In my talk I will explain some of our results, e.g. the existence of functional equations in a suitable global setting, and discuss open problems. In particular, I will indicate how piecing together information about local zeta functions allows us to determine the precise abscissa of convergence for the representation zeta function of the arithmetic group SL3(Z).

I will talk about some ongoing work, motivated by a long standing problem in

the theory of dynamical systems. In particular, I will explain how p-adic

methods lead to the construction of elements in SL_n(Z) whose eigenvalues e_1,

., e_n generate a free abelian subgroup of rank n-1 in the multiplicative group

of positive real numbers. This is a special instance of a more general theorem,

asserting the existence of strongly hyperbolic elements in arithmetic subgroups

of SL_n(R).