Some of Paul Erdős' conjectures

  1. A square cannot be dissected into squares of different sizes.
  2. Let f(n) be the maximum of the sum a1+...+an where a1,...,an are the side lengths of n squares inscribed into a unit square with no common interior point. Show that
  3. If a point is given in a triangle and its distences from the sides are x,y,z, from the nodes are a,b,c then
    a+b+c ≥ 2(x+y+z)
    holds. (Erdős-Mordell inequality)
  4. There are no three consecutive powerful numbers. (Erdős-Mollin-Walsh, a natural number is powerful if no prime divides it on the first power)
  5. If, in an infinite graph, a and b are two vertices which are not joined, then there are a family P of disjoint paths connecting a and b, and a set S of vertices separating a and b such that every path in P contains exactly one element of S and every vertex in S is on a path in P. (Generalized Menger-theorem)
  6. If the sum of reciprocals of a sequence of natural numbers diverges then that sequences contains arbitrarily long arithmetic progressions.
  7. There is a covering system all whose moduli are larger than a predetermined number.
  8. There are infinitely many natural numbers n such that
    holds. (d(n) is the number of positive divisors of n.) (Erdős-Mirsky conjecture)
  9. There are infinitely many natural numbers n such that
    holds (σ(n) is the sum of the positive divisors of n).
  10. Every positive rational number of the form 4/b is the sum of at most 3 unit fractions. (Erdős-Straus)
  11. There is a sequence of natural numbers with distinct pairwise sums (a Sidon sequence) which has more than x1/2-ε elements below x (for every ε>0).
  12. There is a constant c such that for every ε>0, for n large enough the diagonal Ramsey number satisfies
    (c-ε)n < R(n,n) < (c+ε)n.
  13. If, in a graph of nk vertices every vertex has degree less than k, then there is a coloring with k colors such that every color class has exactly n vertices. (Hajnal-Szemerédi theorem)
  14. Given n points on the plane, the number of unit distances between them is O(n1+o(1)).
  15. If a graph is the union of n complete graphs of size n with any two intersecting in at most one vertex, then the graph is n-chromatic. (Erdős-Faber-Lovász-conjecture)
  16. If, in a finite graph, every vertex has degree at least 3, then there is a circuit with length a power of 2. (Erdős-Gyárfás)
  17. For every natural number k there is a constant c such that for every n among cn n-element sets there are k which form a delta-system. (Erdős-Rado)
  18. If A=a0, a1,... is a sequence converging to 0, then there is a set of reals, with positive measure, that does not contain a subset similar to A.
  19. Every uncountably chromatic graphs has an uncountably chromatic triangle-free subgraph.
  20. For any two uncountably chromatic graphs there is a common 4-chromatic subgraph.
  21. Every uncountably chromatic graph contains an infinitely connected subgraph.