Activities This Week

We will define the “lexicographic product” of two structures and show that if both structures admit quantifier elimination, then so does their product. As a corollary we get that nice (model theoretic) properties such as (ultra)homogeneity, stability, NIP and more are preserved under taking products.

It is clear how to iterate the product finitely many times, but we will introduce a new infinite product construction which, while not preserving quantifier elimination, does preserve (ultra)homogeneity. As time allows, we will use this to give a negative answer to the last open question from a paper by A. Hasson, M. Kojman and A. Onshuus who asked ``Is there a rigid elementarily indivisible* structure?’’

As time allows, we will introduce an approach for using the lexicographic product to generalize a result by Lachlan and Shelah to the following: given a finite relational language L, denote by H(L) the class of countable ultrahomogeneous stable L-structures. For M in H(L), define the rank of M to be the maximum value of CR(p,2) where p is a complete 1-type and CR(p,2) is the Shelah’s complete rank. There is a uniform finite bound on the rank of M, where M ranges over H(L). The result was proven by Lachlan and Shelah for L binary and proven in general by Lachlan using the Classification Theorem for finite simple groups.

• A structure M is said to be elementarily indivisible structure if for every colouring of its universe in two colours, there is a monochromatic elementary substructure N of M such that N is isomorphic to M.

The classical Helly’s theorem states that if in a family of compact convex sets in R^d every $d+1$ members have a non-empty intersection then the whole family has a non-empty intersection.

In an attempt to generalize Helly’s theorem, in 1957 Hadwiger and Debrunner posed a conjecture that was proved more than 30 years later in a celebrated result of Alon and Kleitman: For any p,q (p >= q > d) there exists a constant C=C(p,q,d) such that the following holds: If in a family of compact convex sets, out of every p members some q intersect, then the whole family can be pierced with C points. Hadwiger and Debrunner themselves showed that if q is very close to p, then $C=p-q+1$ suffices.

The proof of Alon and Kleitman yields a huge bound $C=O(p^{d^2+d})$, and providing sharp upper bounds on the minimal possible C remains a wide open problem.

In this talk we show an improvement of the best known bound on C for all pairs $(p,q)$. In particular, for a wide range of values of q, we reduce C all the way to the almost optimal bound p-q+1<=C<=p-q+2. This is the first near tight estimate of C since the 1957 Hadwiger-Debrunner theorem.

Joint work with Chaya Keller and Gabor Tardos.

בשנת 1990 קיבל וון ג’ונס את פרס פילדס היוקרתי על המצאת פולינום שמבדיל בין הקשרים. בהרצאה נדון באינווריאנטות שונות של קשרים ודרכים לחשב אותן