Graph of number pairs summing to a square number

Ask Question

Asked 3 years, 10 months ago

Modified 3 years, 10 months ago

Viewed 180 times

Consider the set $\mathbb{Z}_+$ of positive integers and set $E = \big\{\{a,b\}: a\neq b\in\mathbb{Z}_+ \text{ and there is } n\in\mathbb{Z}_+: a+b = n^2\big\}$.

Does the graph $G=(\mathbb{Z}_+,E)$ have cliques of arbitrary sizes? If not, what is its chromatic number?

asked Feb 13, 2021 at 15:44

Dominic van der Zypen

48.9k8 gold badges47 silver badges162 bronze badges

10

$\begingroup$ The clique number is an open problem of Erdos and Moser. Choudhry constructed infinitely many sextuples here worldscientific.com/doi/abs/10.1142/S1793042115500281 $\endgroup$
– Vlad Matei
Commented Feb 13, 2021 at 16:38
1

$\begingroup$ See also math.stackexchange.com/q/1576986 $\endgroup$
– Max Alekseyev
Commented Feb 13, 2021 at 16:43
2

$\begingroup$ Also Bombieri Lang would suggest that the clique number is finite. $\endgroup$
– Vlad Matei
Commented Feb 13, 2021 at 16:45
1

$\begingroup$ I suppose, this should be known for the (positive) differences? $\endgroup$
– Seva
Commented Feb 13, 2021 at 19:16
2

$\begingroup$ This last question also showed up on MathOverflow mathoverflow.net/questions/374394/… $\endgroup$
– Vlad Matei
Commented Feb 13, 2021 at 19:44

| Show 4 more comments

Stack Exchange Network

Graph of number pairs summing to a square number

0

You must log in to answer this question.

Browse other questions tagged
nt.number-theory
graph-theory
graph-colorings
infinite-combinatorics
.

Linked

Graph of number pairs summing to a square number

0

You must log in to answer this question.

Browse other questions tagged nt.number-theorygraph-theorygraph-coloringsinfinite-combinatorics.

Linked

Related

Browse other questions tagged
nt.number-theory
graph-theory
graph-colorings
infinite-combinatorics
.