L6

Exponents of Diophantine approximation are defined to study specific sets of real numbers for which Dirichlet's pigeonhole principle can be improved. Khintchine stated a transference principle between the two exponents in the cases  of simultaneous approximation and approximation by linear forms. This shows that exponents of Diophantine approximation are related, and these relations can be studied via so called spectra. In this talk, we provide an optimal bound for the ratio between ordinary and uniform exponents of Diophantine approximation for both simultaneous approximation and approximation by linear forms. This is joint work with Nikolay Moshchevitin.

It is an old problem in number theory to count number fields of a fixed degree and having a fixed Galois group for its Galois closure, ordered by their absolute discriminant, say. In this talk, I shall discuss some background of this problem, and then report a recent work with Stanley Xiao. In our paper, we considered quartic $D_4$-fields whose ring of integers has a certain nice algebraic property, and we counted such fields by their conductor.

Let $P$ be a random polynomial of degree $d$ such that the leading and constant coefficients are 1 and the rest of the coefficients are independent random variables taking the value 0 or 1 with equal probability. Odlyzko and Poonen conjectured that $P$ is irreducible with probability tending to 1 as $d$ grows.  I will talk about an on-going joint work with Emmanuel Breuillard, in which we prove that GRH implies this conjecture. The proof is based on estimates for the mixing time of random walks on $\mathbb{F}_p$, where the steps are given by the maps $x \rightarrow ax$ and $x \rightarrow ax+1$ with equal probability.

Let $f_1,\dots,f_k$ be real polynomials with no constant term and degree at most $d$. We will talk about work in progress showing that there are integers $n$ such that the fractional part of each of the $f_i(n)$ is very small, with the quantitative bound being essentially optimal in the $k$-aspect. This is based on the interplay between Fourier analysis, Diophantine approximation and the geometry of numbers. In particular, the key idea is to find strong additive structure in Fourier coefficients.

It is difficult to determine when a graph G can be edge-covered by edge-disjoint copies of a fixed graph F. That is, when it has an F-decomposition. However, if G is large and has a high minimum degree then it has an F-decomposition, as long as some simple divisibility conditions hold. Recent research allows us to prove bounds on the necessary minimum degree by studying a relaxation of this problem, where a fractional decomposition is sought.

I will show how a relatively simple random process can give a good approximation to a fractional decomposition of a dense graph, and how it can then be made exact. This improves the best known bounds for this problem.
 

Consider a family of k-element subsets of an n-element set, and assume that the family does not contain s pairwise disjoint sets. The well-known Erdos Matching Conjecture suggests the maximum size of such a family. Finding the maximum is trivial for n<(s+1)k and is relatively easy for n large in comparison to s,k. There was a splash of activity around the conjecture in the recent years, and, as far as the original question is concerned, the best result is due to Peter Frankl, who verified the conjecture for all n>2sk. In this work, we improve the bound of Frankl for any k and large enough s. We also discuss the connection of the problem to an old question on deviations of sums of random variables going back to the work of Hoeffding and Shrikhande.
 

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an 'enlarged' copy H^+ of a fixed hypergraph H. These include well-known  problems such as the Erdős-Sós 'forbidding one intersection' problem and the Frankl-Füredi 'special simplex' problem.

In this talk we present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove that any (H^+)-free hypergraph is essentially contained in a 'junta' -- a hypergraph determined by a small number of vertices -- that is also (H^+)-free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes  the aforementioned problems, and solves them for a large new set of parameters.

Based on joint works with David Ellis and Nathan Keller
 

We prove that the dimension of every poset whose comparability graph has maximum degree $\Delta$ is at most $\Delta\log^{1+o(1)} \Delta$. This result improves on a 30-year old bound of F\"uredi and Kahn, and is within a $\log^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\Delta$ has boxicity at most $\Delta\log^{1+o(1)} \Delta$, which is also within a $\log^{o(1)}\Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\Theta(\sqrt{g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor. This is joint work with Alex Scott (arXiv:1804.03271).

When studying a group, it is natural and often useful to try to cut it up 
onto simpler pieces. Sometimes this can be done in an entirely canonical 
way analogous to the JSJ decomposition of a 3-manifold, in which the 
collection of tori along which the manifold is cut is unique up to isotopy. 
It is a theorem of Brian Bowditch that if the group acts nicely on a metric 
space with a negative curvature property then a canonical decomposition can 
be read directly from the large-scale geometry of that space. In this talk 
we shall explore an algorithmic consequence of this relationship between 
the large-scale geometry of the group and is algebraic decomposition.