# Tag Archives: Paul Erdos

# Some old and new problems in combinatorics and geometry

**Paul Erdős in Jerusalem, 1933 1993**

Update: Here is a link to a draft of a paper* based on the first part of this lecture. Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.

I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and new problems (mainly) in combinatorics and geometry (here are the slides), where I presented twenty problems, here they are:

## Around Borsuk’s Problem

Let be the smallest integer so that every set of diameter one in can be covered by sets of smaller diameter. Borsuk conjectured that .

It is known (Kahn and Kalai, 1993) that : , and also that (Schramm, 1989) .

**Problem 1:** Is *f(d)* exponential in *d*?

**Problem 2:** What is the smallest dimension for which Borsuk’s conjecture is false?

## Volume of sets of constant width in high dimensions

**Problem 3:** Let us denote the volume of the n-ball of radius 1/2 by .

**Question** (Oded Schramm): Is there some so that for every there exist a set of constant width 1 in dimension n whose volume satisfies .

## Around Tverberg’s theorem

Tverberg’s Theorem states the following: Let be points in with . Then there is a partition of such that .

**Problem 4:** Let be the smallest integer such that given points in , there exists a partition of such that every among the convex hulls , have a point in common.

Reay’s“relaxed Tverberg conjecture” asserts that that whenever (and ), .

**Problem 5: **For a set , denote by those points in which belong to the convex hull of pairwise disjoint subsets of . We call these points **Tverberg points of order** .

Conjecture:For every , .

Note that .

**Problem 6:** How many points in guarantee that they can be divided into two parts so that every union of convex sets containing the first part has a non empty intersection with every union of convex sets containing the second part.

## A question about directed graphs

**Problem 7:** Let *G* be a directed graph with *n* vertices and *2n-2* edges. When can you divide your set of edges into two trees and (so far we disregard the orientation of edges,) so that when you reverse the directions of all edges in you get a strongly connected digraph.

## Erdős-Ko-Rado theorem meets Catalan

**Problem 8 **

**Conjecture:** Let be a collection of triangulations of an *n*-gon so that every two triangulations in share a diagonal. Then is at most the number of triangulations of an *(n-1)*-gon.

## F ≤ 4E

**Problem 9:** Let *K* be a two-dimensional simplicial complex and suppose that *K* can be embedded in . Denote by *E* the number of edges of *K* and by *F* the number of 2-faces of K.

**Conjecture: ****F ****≤** 4E

A weaker version which is also widely open and very interesting is: For some absolute constant *C*, *F ≤ C E.*

## Polynomial Hirsch

**Problem 10: **The diameter of graphs of *d*-polytopes with *n* facets is bounded above by a polynomial in *d* and *n*.

## Analysis – Fixed points

**Problem 11:** Let *K* be a convex body in . (Say, a ball, say a cube…) For which classes of functions, every which takes *K* into itself admits a fixed point in *K*.

## Number theory – infinitely many primes in sparse sets

**Problem 12**: Find a (not extremely artificial) set *A* of integers so that for every *n*, , where you can prove that *A* contains infinitely many primes.

## Möbius randomness for sparse sets

**Problem 13:** Find a (not extremely artificial) set *A* of integers so that for every *n*, where you can prove that

## Computation – noisy game of life

**Problem 14:** Does a noisy version of Conway’s game of life support universal computation?

## Ramsey for polytopes

**Problem 15: **

**Conjecture:** For a fixed *k,* every *d*-polytope of sufficiently high dimension *d *contains a *k*-face which is either a simplex or a (combinatorial) cube.

## Expectation thresholds and thresholds

**Problem 16:** Consider a random graph *G* in **G(n,p)** and the graph property: *G* contains a copy of a specific graph *H*. (Note: *H* depends on *n*; a motivating example: *H* is a Hamiltonian cycle.) Let *q* be the minimal value for which the expected number of copies of *H’* in *G in ***G(n,q)** is at least 1/2 for every subgraph *H’* of *H*. Let *p* be the value for which the probability that *G* in **G(n,p)** contains a copy of *H* is 1/2.

**Conjecture:** [Kahn – Kalai 2006] *p/q = O( *log* n)*

## Traces

**Problem 17:** Let *X* be a family of subsets of .

How large *X* is needed to be so that the restriction (trace) of *X* to some set , has at least elements?

## Graph-codes

**Problem 18:** Let ** P** be a property of graphs. Let be a collection of graphs with* n* vertices so that the symmetric difference of two graphs in has property **P**. How large can be.

## Conditions for colorability

**Problem 19: **A conjecture by Roy Meshulam and me:

There is a constant *C* such that every graph *G*

with no induced cycles of order divisible by 3 is colorable by *C* colors.

**Problem 20:**

Another conjecture by Roy Meshulam and me: For every *b>0* there

is a constant *C=C(b)* with the following property:

Let *G* be a graph such that for all its induced subgraphs *H*

The number of independent sets of odd size minus the number of independent sets of even size is between-bandb.

Then *G* is colorable by *C(b)* colors.

## Remarks:

The title of the lecture is borrowed from several papers and talks by Erdős. Continue reading

# Erdős’ Birthday

Paul Erdős was born on March 26, 1913 ~~2013~~ a hundred years ago. This picture (from Ehud Friedgut’s homepage) was taken in September ’96 in a Chinese restaurant in Warsaw, a few days before Paul Erdős passed away. The other diners are Svante Janson, Tomasz Łuczack and Ehud Friedgut. Erdős’ influence is felt everywhere in combinatorics, mathematics as a whole, and this blog as well. (A few more links: my most decorated MO answer is about Erdős, a recent heated discussion on the “two cultures in mathematics,” a new post on Erdős discrepancy problem on GLL, and, **most important, a link to Erdős centennial conference, in Budapest July 1-5, 2013**. Join the celebration!)

Do not hesitate to contribute a comment!

# Extremal Combinatorics I: Extremal Problems on Set Systems

The “basic notion seminar” is an initiative of David Kazhdan who joined HU math department around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. I gave two lecture series, one about “computational complexity theory” a couple of years ago, and one about extremal combinatorics or Erdös-type combinatorics a few months ago, which later I expanded to a series of five+one talks at Yale. One talk was on the Borsuk Conjecture, which I will discuss separately, and five were titled: “Extremal Combinatorics: A working tool in mathematics and computer science.” Let me try blogging about it. The first talk was devoted to extremal problems concerning systems of sets.

** **

** **

** **Paul Erdös

### 1. Three warm up problems

Here is how we move very quickly from very easy problems to very hard problems with a similar flavour.

**Problem I**: Let N = {1,2, … , n } . What is the largest size of a family of subsets of such that every two sets in have non empty intersection? (Such a family is called *intersecting*.)