L6

We purify and generalize some techniques which were successful in the limit theory of graphs and other discrete structures. We demonstrate how this technique can be used for solving different combinatorial problems, by defining the limit problems of the Manickam--Miklós--Singhi Conjecture, the Kikuta–Ruckle Conjecture and Alpern's Caching Game.

Many of the fastest known algorithms for factoring large integers rely on finding subsequences of randomly generated sequences of integers whose product is a perfect square. Motivated by this, in 1994 Pomerance posed the problem of determining the threshold of the event that a random sequence of N integers, each chosen uniformly from the set
{1,...,x}, contains a subsequence, the product of whose elements is a perfect square. In 1996, Pomerance gave good bounds on this threshold and also conjectured that it is sharp.

In a paper published in Annals of Mathematics in 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In recent work, we have confirmed this conjecture. In my talk, I shall give a brief overview of some of the ideas used in the proof, which relies on techniques from number theory, combinatorics and stochastic processes. Joint work with Béla Bollobás and Robert Morris.

For a fixed degree sequence D=(d_1,...,d_n), let G(D) be a uniformly chosen (simple) graph on {1,...,n} where the vertex i has degree d_i. The study of G(D) is of special interest in order to model real-world networks that can be described by their degree sequence, such as scale-free networks. While many aspects of G(D) have been extensively studied, most of the obtained results only hold provided that the degree sequence D satisfies some technical conditions. In this talk we will introduce a new approach (based on the switching method) that allows us to study the random graph G(D) imposing no conditions on D. Most notably, this approach provides a new criterion on the existence of a giant component in G(D). Moreover, this method is also useful to determine whether there exists a percolation threshold in G(D). The first part of this talk is joint work with F. Joos, D. Rautenbach and B. Reed, and the second part, with N. Fountoulakis and F. Joos.

For any given graph H, we may define a natural corresponding functional ||.||_H. We then say that H is norming if ||.||_H is a semi-norm. A similar notion ||.||_{r(H)} is defined by || f ||_{r(H)}:=|| | f | ||_H and H is said to be weakly norming if ||.||_{r(H)} is a norm. Classical results show that weakly norming graphs are necessarily bipartite. In the other direction, Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. Using results from the theory of finite reflection groups, we demonstrate that any graph which is edge-transitive under the action of a certain natural family of automorphisms is weakly norming. This result includes all previous examples of weakly norming graphs and adds many more. We also include several applications of our results. In particular, we define and compare a number of generalisations of Gowers' octahedral norms and we prove some new instances of Sidorenko's conjecture. Joint work with David Conlon.

Given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs? This question is a natural graph-theoretic generalisation of the 'multiplication table problem' of Erdős:  Erdős’s problem of estimating the number of distinct products a.b with a, b in [n] is precisely the problem under consideration when the graph in question is the complete bipartite graph K_{n,n}.

Based on joint work with J. Sahasrabudhe and I. Tomon.

The concept of pseudofinite dimension for ultraproducts of finite structures was introduced by Hrushovski and Wagner. In this talk, I will present joint work with D. Macpherson and C. Steinhorn in which we explored conditions on the (fine) pseudofinite dimension that guarantee simplicity or supersimplicity of the underlying theory of an ultraproduct of finite structures, as well as a characterization of forking in terms of droping of the pseudofinite dimension. Also, under a suitable assumption, it can be shown that a measure-theoretic condition is equivalent to loc

*/ /*-->*/ A {\em monoid} is a semigroup with identity. A {\em finitary property for monoids} is a property guaranteed to be satisfied by any finite monoid. A good example is the maximal condition on the lattice of right ideals: if a monoid satisfies this condition we say it is {\em weakly right noetherian}. A monoid $S$ may be represented via mappings of sets or, equivalently and more concretely, by {\em (right) $S$-acts}. Here an $S$-act is a set $A$ together with a map $A\times S\rightarrow A$ where $(a,s)\mapsto as$, such that

for all $a\in A$ and $s,t\in S$ we have $a1=a$ and $(as)t=a(st)$. I will be speaking about finitary properties for monoids arising from model theoretic considerations for $S$-acts.

Let $S$ be a monoid and let $L_S$ be the first-order language of $S$-acts, so that $L_S$ has no constant or relational symbols (other than $=$) and a unary function symbol $\rho_s$ for each $s\in S$. Clearly $\Sigma_S$ axiomatises the class of $S$-acts, where

\[\Sigma_S=\big\{ (\forall x)(x\rho_s \rho_t=x\rho_{st}):s,t\in S\big\}\cup\{ (\forall x)(x\rho_1=x)

\}.\]

Model theory tells us that $\Sigma_S$

has a model companion $\Sigma_S^*$ precisely when the class

${\mathcal E}$ of existentially closed $S$-acts is axiomatisable and

in this case, $\Sigma_S^*$ axiomatises ${\mathcal E}$. An old result of Wheeler tells us that $\Sigma_S^*$ exists if and only if for every finitely generated right congruence $\mu$ on $S$, every finitely generated $S$-subact of $S/\mu$ is finitely presented, that is, $S$ is {\em right coherent}. Interest in right coherency also arises from other considerations such as {\em purity} for $S$-acts.

Until recently, little was known about right coherent monoids and, in particular, whether free monoids are (right) coherent.

I will present some work of Gould, Hartmann and Ru\v{s}kuc in this direction: specifically we answer positively the question for free monoids.

Where $\Sigma_S^*$ exists, it is known to be

stable, and is superstable if and only if $S$ is weakly right noetherian.

By using an algebraic description of types over $\Sigma_S^*$ developed in the 1980s by Fountain and Gould,

we can show that $\Sigma_S^*$ is totally

transcendental if and only if $S$ is weakly right noetherian and $S$ is {\em ranked}. The latter condition says that every right congruence possesses a finite Cantor-Bendixon rank with respect to the {\em finite type topology}.

Our results show that there is a totally transcendental theory of $S$-acts for which Morley rank of types does not coincide with $U$-rank, contrasting with the corresponding situation for modules over a ring.

I will consider automorphism groups of countable structures acting continuously on compact spaces: the viewpoint of topological dynamics. A beautiful paper of Kechris, Pestov and Todorcevic makes a connection between this and the ‘structural Ramsey theory’ of Nesetril, Rodl and others in finite combinatorics. I will describe some results and questions in the area and say how the Hrushovski predimension constructions provide answers to some of these questions (but then raise more questions). This is joint work with Hubicka and Nesetril.

An abelian l-group G is essentially a partially ordered subgroup of functions from a set to a totally ordered abelian group such

that G is closed under taking finite infima and suprema. For example, G could be the continuous semi-linear functions defined on the open
unit square, or, G could be the continuous semi-algebraic functions defined in the plane with values in (0,\infty), where the group
operation is multiplication. I will show how G, under natural geometric assumptions, can be interpreted (in a weak sense) in its lattice of
zero sets. This will then be applied to the model theory of natural divisible abelian l-groups. For example we will see that the
aforementioned examples are elementary equivalent. (Parts of the results have been announced in a preliminary report from 1987 by F. Shen
and V. Weispfenning.)