Questions tagged [erdos]

For questions related to the work of Paul Erdős, especially the many results and conjectures which bear his name.

32 questions
Filter by
Sorted by
Tagged with
473 views

Are there 100 points that are part of every half-density part of the plane?

Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$? I am deliberately being vague ...
• 18.2k
434 views

Extension of Erdős-Gallai (s,t)-path theorem to directed graphs

The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498): Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
186 views

Happy ending problem - why not a proof by induction? (cont)

After sharing ideas on this post, I have been thinking for some time on the problem, and I think that a possible way to prove the Erdös-Szekeres conjecture could be structured as follows: Consider ...
• 219
625 views

List of problems that Erdős offered money for?

Is there a list somewhere of all the problems that Erdős offered cash awards for, including both solved and unsolved problems? One would think that the answer is yes, but so far I have had no luck ...
• 77.9k
121 views

Quasi-ideals and Erdős conjecture on arithmetic progressions

Starting to read a book about algebraic geometry as well as the Wikipedia article on Erdős conjecture on arithmetic progressions, I came to think of what follows. Let $A$ be a set of positive integers,...
• 6,936
288 views

• 11.2k
586 views

A limit from an Erdos paper

Hi, I need help to prove that, for $N = \big\lfloor \frac{1}{2}n\log(n)+cn \big\rfloor$ with $c \in \mathbb R$ and $0 \leq k \leq n:$  \lim_{n\rightarrow +\infty} \dbinom{n}{k} \frac{\dbinom{\...
• 21
706 views

Paul Erdős and Ramanujan Primes

It's easy to find Ramanujan's proof of Ramanujan primes: Ramanujan's Proof Wikipedia mentions that Paul Erdős also had a proof: Wikipedia article on Bertrand's Postulate Does anyone know the ...
• 1,039
493 views

A question about the number of intersections of lines in $R^{3}$

Suppose I have n lines in $R^{3}$ with the conditions that: no 3 lines in one plane, no 3 lines intersect at one point, for fixed 2 lines, no 3 lines intersect these 2 lines at the same time. what is ...
• 215
446 views

Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane

In the middle of page 9 of http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf. They said " Now we select a random subset....choosing lines independently with probability $\frac{Q}{100}$. With ...
• 215
2k views

Erdos distance problem n=12

The recent paper On the Erdos distinct distance problem in the plane Authors: Larry Guth, Nets Hawk Katz prodded me to get a non-trivial example. Here is what I cannot find: an example of 12 ...
• 161
349 views

Determining the vector space for application of Cauchy Schwarz

In the paper "On the Erdős distinct distance problem in the plane" by Larry Guth and Nets Hawk Katz, http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf they define the functions $d(P)$, (...
• 323