# Questions tagged [erdos]

The erdos tag has no usage guidance.

The erdos tag has no usage guidance.

30
questions

4
votes

0
answers

136
views

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 ...

12
votes

0
answers

383
views

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 ...

2
votes

0
answers

115
views

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,...

2
votes

1
answer

180
views

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}$...

5
votes

2
answers

284
views

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 ...

0
votes

1
answer

191
views

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$ ...

4
votes

0
answers

420
views

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$}\}...

13
votes

2
answers

561
views

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$ ...

5
votes

1
answer

366
views

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 $...

36
votes

2
answers

4k
views

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, ...

16
votes

2
answers

1k
views

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 ...

0
votes

1
answer

655
views

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 ...

12
votes

0
answers

400
views

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 ...

2
votes

0
answers

158
views

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 ...

2
votes

1
answer

536
views

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 ...

1
vote

1
answer

311
views

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 ...

16
votes

2
answers

2k
views

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 ...

14
votes

1
answer

3k
views

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 ...

30
votes

2
answers

3k
views

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 ...

2
votes

3
answers

581
views

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{\...

3
votes

0
answers

691
views

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 ...

3
votes

1
answer

488
views

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 ...

4
votes

1
answer

442
views

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 ...

15
votes

3
answers

2k
views

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 ...

2
votes

2
answers

340
views

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)$, (...

13
votes

2
answers

888
views

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 < ...

37
votes

4
answers

3k
views

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 ...

3
votes

1
answer

808
views

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. ...

15
votes

6
answers

4k
views

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 ...

26
votes

5
answers

8k
views

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 ...