Workshop on Euclidean Ramsey Theory

Abstract: By a distance graph in a metric space I mean, as usual, a graph, whose set of vertices lies in a set X endowed with a metric d and whose set of edges is formed by all pairs of vertices at a certain distance or even at a distance from a prescribed set of positive numbers. Distance graphs are closely related with various aspects of modern Ramsey theory, especially in its geometric part. In my talk, I'll give a survey of various extremal problems concerning distance graphs, space colorings, and Ramsey numbers in some geometric settings.

Abstract: A planar set A is called 1-avoiding if the distance between any two points of A is not equal to 1. What is the maximal possible density of such a set A? According to an old conjecture of Erdos it is less than 0.25. The best known construction is due to Croft and it has density 0.229... In this talk I will review recent developments of the upper bound getting very close to 0.25. Interestingly, there are two different techniques, giving very similar numerical upper bounds: one using Fourier analysis, and the other using fractional chromatic numbers of unit distance graphs. Yet, neither technique could so far reach the conjectured upper bound of 0.25. Joint work with Gergely Ambrus

Abstract: Which domains in Euclidean space admit an orthogonal basis of exponential functions? For example, the cube is such a domain, but the ball is not. In 1974, Fuglede made a fascinating conjecture that these domains could be characterized geometrically as the domains which can tile the space by translations. While this conjecture was disproved for general sets, in a recent paper with Máté Matolcsi we did prove that Fuglede's conjecture is true for convex domains in all dimensions. I will survey the subject and discuss this result.

Abstract: Ramsey theory has many faces, including graph Ramsey theory, arithmetic Ramsey theory and Euclidean Ramsey theory. In this talk, we describe recent results from each of these three areas.

Abstract: How can you tell if someone is an expert? If X is more talented than Y? Maybe they are just guessing (or just got lucky). In joint work with the wonderful Ron Graham, over a 40 year period, we studied a model version of this problem. In this talk, I'll tell you what we learned. The problem involves an ordinary deck of 52 cards. They are well shuffled and looked at one at a time. Each time, a guesser tries to guess the next card (before it is discarded) and is told if the guess is right or wrong. How should the guesser use this information to get a high score? For all our study, we don't know the exact best thing to do(!). NEXT, how can we judge if the guesser 'has talent'? A very useful notion of 'skill scoring' helps to solve this problem. I'll explain how this has applications to taste testing experiments, to evaluation of clinical trials and to testing if 'extra sensory perception' is a real phenomenon.

Abstract: The famous conjecture of Erdos, Graham, Montgomery, Rothschild, Spencer and Straus is that a set is Ramsey if and only if it embeds in a sphere. Here as usual `Ramsey' means that for every k there is an n such that whenever we k-colour real n-dimensional space there is a copy of the set that is monochromatic. We propose a `rival' conjecture, that a set is Ramsey if and only if it embeds into a (finite) transitive set. We will discuss the motivation for this conjecture, as well as how it relates to the original conjecture. (Joint work with Paul Russell and Mark Walters).

Abstract: Graham conjectured that for every finite subset F of the unit sphere S^n, every eps>0, and every number of colours r there exists a dimension N=N(F, eps, r) such that no matter how the points of an N-dimensional sphere of radius 1+eps are coloured with r colours, there exists a monochromatic congruent copy of F. We discuss some results motivated by this problem.

Abstract: Recently I made the first improvement since 1950 to the bounds of the Hadwiger-Nelson problem, which is to determine the chromatic number of the plane (CNP); the lower bound was previously 4, since there are 4-chromatic unit-distance graphs (UDGs) in the plane. The improvement to CNP>=5 was achieved by identifying, though not actually defining precisely, a numerical function of UDGs that seemed likely to be high in some 4-chromatic cases and low in others, and using examples of the two classes as building-blocks. One of the classes required computer search to identify, and the smallest 5-chromatic graph that I found has 1581 vertices. Interest has immediately been high in identifying simpler cases, and a Polymath project was created for this purpose, which has also explored related questions. I shall describe the initial discovery and the project's recent progress.

Abstract: Given C, a convex closed curve that is symmetric with respect to the origin in the Euclidean plane, consider M(C), the Minkowski metric space with C as a unit circle. We are interested in the chromatic number of this space, which is the minimum number of colors required to color the points of the plane so that any two points at C-distance exactly 1 receive different colors. Chilakamarri proved that for any centrally symmetric convex curve C, the chromatic number of M(C) is between 4 and 7, and that if C is either a parallelogram or a centrally symmetric hexagon then the chromatic number of M(C) is 4. From the recent work of de Grey, it is now known that the chromatic number of the plane with the Euclidean metric is at least 5; we know however of no other curve C, for which the chromatic number of M(C) satisfies this inequality. Among other things, we will show that if C is a regular octagon then at least 5 colors are needed to properly color M(C). This is joint work with Geoffrey Exoo.

Abstract: The title problem is hard. It has an exciting birth, fascinating history, inspiring spin-off problems, colorful personalities of contributors, and even one known detractor. I’ll touch on some of these facets. We, humans, sometimes give credits where credits aren’t due, and all too often deny credits to those who pave the way by posing right problems and formulating inspiring conjectures. I wonder, what would a problem solver solve if there were no problem? Ron Graham believed that every talk has to include a proof, and a touch of humor. I will follow his example. This talk is dedicated to the loving memory of our Captain Ron Graham.

Abstract: We present a brief survey on how the Axiom of Choice can be applied to produce various strange sets and decompositions in Euclidean spaces.

Abstract: The classical Steinhaus problem asks if there is a set in the plane meeting every isometric copy of the integer lattice in exactly one point. Jackson and Mauldin showed in ZFC that such sets exist. The corresponding problem in one dimension had been shown earlier by Komjath. In higher dimensions, the result holds for some lattices but not others. The problem can be generalized by replacing lattices with other sets. One particularly interesting variation is when the lattice is replaced by a finite set. This is known as the finite Steinhaus set problem. The theorem is conjectured to hold for all finite sets, but this is known for sets of sizes 2,3,4,5,7. There is a connection between this problem and certain algebraic structures called pseudo abelian groups.

Abstract: Let C be a finite set in R^d. Our central question is how many colors do we need to paint R^n (n >= d) so that there is no monochromatic set congruent to C. We call this quantity the chromatic number of R^n with forbidden set C. When C consists of two points at distance one, then this is the usual chromatic number of R^n. In my talk I will discuss how we can obtain upper bounds for these quantities. Additionally I will explain how we can get better bounds if we replace R^n with a Euclidean ball of radius r.

Abstract: By analogy with Euclidean Ramsey theory, we ask the following general question: given a metric space X, what is the smallest number of colors needed to color R^d_{infty} (i.e., the d-dimensional real affine space with maximum norm) so that the coloring does not contain a monochromatic isometric copy of X? We show that for any finite metric space X this number is exponential in d. We also relate it to several intriguing finite combinatorial problems and show that, to a large extent, this question is 1-dimensional. Joint work with Nóra Frankl and Arsenii Sagdeev.

Abstract: In the first half of the talk we consider some results about the maximum density of a subset of Z that does not contain a congruent copy of a given finite set H. In particular, we prove a conjecture of Schmidt and Tuller about the |H|=3 case. These one dimensional results are related to the chromatic number of d-dimensional space with the max norm. This part is joint work with Andrey Kupavskii and Arsenii Sagdeev. In the second half of the talk we consider questions that are related to the chromatic number of the Euclidean plane. Let S be a finite subset of R^d and p be a point of S. In a colouring of R^d we call the pair (S,p) almost monochromatic, if S\{p} is monochromatic, but S is not. We consider questions about finding almost monochromatic similar copies of a given pair (S,p) under certain restrictions on the colouring. These questions were originally motivated by finding a human verifiable proof of chi(R^2)>4, but are also interesting on their own right. This part is joint work with Tamás Hubai and Dömötör Pálvölgyi.