Questions tagged [erdos]

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

Filter by
Sorted by
Tagged with
11 votes
0 answers
479 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 ...
domotorp's user avatar
  • 18.3k
8 votes
0 answers
435 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 ...
Nicole Wein's user avatar
4 votes
0 answers
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 ...
Juan Moreno's user avatar
13 votes
0 answers
641 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 ...
Timothy Chow's user avatar
2 votes
0 answers
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,...
Sylvain JULIEN's user avatar
3 votes
1 answer
298 views

Probabilistic bound to the number of edge disjoint triangles in a random graph

Let $G$ be a random graph with $n$ vertices, and let $\delta(G)$ be the maximum number of triangles in $G$. Question. How to prove the bound $$P(\delta(G)) \leq m - t \sqrt{f(m)}) \leq 2e^{-t^2 / 4}$...
user avatar
5 votes
2 answers
301 views

Updates on a least prime factor conjecture by Erdos

In the 1993 article "Estimates of the Least Prime Factor of a Binomial Coefficient," Erdos et al. conjectured that $$\operatorname{lpf} {N \choose k} \leq \max(N/k,13)$$ With finitely many ...
Descartes Before the Horse's user avatar
0 votes
1 answer
245 views

Generalized Erdős multiplication table problem

Consider multiplication operation $$f(x_1,\dots, x_k)=\prod_{i=1}^kx_i$$ where $x_i\in\{1,\dots, n_i\}$ with $n_1,\dots, n_k\in\{1,\dots,\infty\}$. What is the cardinality of the range? At $k =2$ ...
VS.'s user avatar
  • 1,816
4 votes
0 answers
435 views

The "core" of complete Erdős space

This question is about the Erdős spaces: $\mathfrak E=\{x\in \ell^2:x_n\in \mathbb Q\text{ for all $n<\omega$}\}$; and $\mathfrak E_c=\{x\in \ell^2:x_n\in \mathbb P\text{ for all $n<\omega$}\}...
D.S. Lipham's user avatar
  • 3,045
13 votes
2 answers
627 views

A reformulation of Erdős conjecture on arithmetic progressions

Erdős conjecture on arithmetic progressions states that if $S$ is a set of positive integers such that $c(S):=\sum_{n \in S} \frac{1}{n} = \infty$ (large set), then $ \forall \ell \ge 3$ the set $S$ ...
Sebastien Palcoux's user avatar
5 votes
1 answer
370 views

Countable version of Erdös-Lovasz-Faber conjecture

Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties: $|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and $|A_n|=\aleph_0$ for all $...
Dominic van der Zypen's user avatar
37 votes
2 answers
4k views

How to find Erdős' treasure trove?

The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...
Morteza Azad's user avatar
16 votes
2 answers
1k views

Is there any published summary of Erdos's published problems in the American Mathematical Monthly journal?

As we know Erdos has proposed a considerable number of problems in the "American Mathematical Monthly" journal. Is there any published summary of Erdos's published problems in the American ...
Martin Bokner's user avatar
0 votes
1 answer
870 views

Random graphs- Erdos and Renyi 1959 paper

Please refer to this link. It is Erdos and Renyi's first paper on Random Graphs (1959). I am trying to work through it. I'm struggling with equations (16), (17) and (21). (16) I'm not sure why ...
Curious_Mel's user avatar
12 votes
0 answers
454 views

On a relaxed form of Goldbach's conjecture proposed by Erdős

The Goldbach's conjecture says that: "Every even integer greater that $2$ is the sum of two prime numbers". Let $\varphi$ denote the Euler's totient function. I remember that a long time ago I read ...
user avatar
2 votes
0 answers
201 views

mixing time of random walks on dense Erdos Renyi graphs

Is there anything known about the mixing time of a simple random walk on an Erdos-Renyi graph with parameter $\langle n,d \rangle$ where $d=n^a (0<a<1 )$. I know about Reed et al and Benjamini ...
shahrzad haddadan's user avatar
2 votes
1 answer
660 views

When an Erdos-Renyi graph is locally tree like?

I would like to know when an ER graph is locally treeing like. In this post. I found this comment: I think $N$ is $\log2|V|$, or something like that, in that paper. They consider binary vectors ...
fdesmond's user avatar
1 vote
1 answer
386 views

estimating binomial coefficients

There is a beautiful paper on the arXiv by Andrew Suk containing an asymptotic result about the Erdös-Szekeres convex polygon problem. I am struggling with one of the estimates he makes on page 4. He ...
Ulrich Pennig's user avatar
16 votes
2 answers
3k views

Many representations as a sum of three squares

Let $r_3(n) = \left|\{(a,b,c)\in {\mathbb Z}^3 :\, a^2+b^2+c^2=n \}\right|$. I am looking for the maximum asymptotic size of $r_3(n)$. That is, the maximum number of representations that a number can ...
Adam Sheffer's user avatar
  • 1,052
14 votes
1 answer
4k views

What is the source of this E̶r̶d̶ő̶s̶ quote?

Namely, the following one "All problems appeared once in the [American Mathematical] Monthly." I remember reading it several years ago... When I first posed the question, I believed that I had ...
José Hdz. Stgo.'s user avatar
31 votes
2 answers
3k views

The Erdős-Turán conjecture or the Erdős' conjecture?

This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics: Conjecture: If $A\subset \mathbb{N}$ and $$\...
Eric Naslund's user avatar
  • 11.2k
2 votes
3 answers
587 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{\...
Bob's user avatar
  • 21
3 votes
0 answers
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 ...
Larry Freeman's user avatar
3 votes
1 answer
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 ...
user13289's user avatar
  • 215
4 votes
1 answer
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 ...
user13289's user avatar
  • 215
15 votes
3 answers
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 ...
jkruso's user avatar
  • 161
2 votes
2 answers
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)$, (...
Chris's user avatar
  • 323
13 votes
2 answers
919 views

Did Erdős publish his proof of the multiplicative version of the Erdős-Turán conjecture?

I read in an article of Erdős ("Extremal problems in number theory") that he had a proof of the multiplicative version of the Erdős-Turán conjecture. The statement of this theorem is Let $a_1 < ...
Gjergji Zaimi's user avatar
39 votes
5 answers
3k views

Does there exist a comprehensive compilation of Erdos's open problems?

Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single ...
Timothy Chow's user avatar
3 votes
1 answer
841 views

A limit involving the totient function

P. Erdős and Leon Alaoglu proved in [1] that for every $\epsilon > 0$ the inequality $\phi(\sigma(n)) < \epsilon \cdot n$ holds for every $n \in \mathbb{N}$, except for a set of density $0$. C. ...
José Hdz. Stgo.'s user avatar
16 votes
6 answers
5k views

If Erdős is published as Erdös in a paper, which do I cite?

There seems to be a few papers around with Erdős written as Erdös. For example: MR0987571 (90h:11090) Alladi, K.; Erdös, P.; Vaaler, J. D. Multiplicative functions and small divisors. II. J. Number ...
27 votes
5 answers
8k views

Erdos Conjecture on arithmetic progressions

Introduction: Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length. Question: I ...
Alex R.'s user avatar
  • 4,902