Skip to main content
added update
Source Link
domotorp
  • 18.8k
  • 3
  • 57
  • 126

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.

Is it true that for every $k$ every long enough path in the grid graph (which is a 4-regular infinite graph) contains a $k$-AP?

The statement holds for $k=4$: https://arxiv.org/abs/2004.12801
and it feels that it should have an easy proof for all $k$, but I don't see it.

Update. As pointed out by Renan in his answer, this problem was already posed and solved by him; the statement fails already for $k=5$: https://sarcasticresonance.wordpress.com/2018/11/21/arithmetic-progressions-in-space-2/

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.

Is it true that for every $k$ every long enough path in the grid graph (which is a 4-regular infinite graph) contains a $k$-AP?

The statement holds for $k=4$: https://arxiv.org/abs/2004.12801
and it feels that it should have an easy proof for all $k$, but I don't see it.

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.

Is it true that for every $k$ every long enough path in the grid graph (which is a 4-regular infinite graph) contains a $k$-AP?

The statement holds for $k=4$: https://arxiv.org/abs/2004.12801
and it feels that it should have an easy proof for all $k$, but I don't see it.

Update. As pointed out by Renan in his answer, this problem was already posed and solved by him; the statement fails already for $k=5$: https://sarcasticresonance.wordpress.com/2018/11/21/arithmetic-progressions-in-space-2/

Became Hot Network Question
Source Link
domotorp
  • 18.8k
  • 3
  • 57
  • 126

Does every big polyomino contain a big arithmetic progression?

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.

Is it true that for every $k$ every long enough path in the grid graph (which is a 4-regular infinite graph) contains a $k$-AP?

The statement holds for $k=4$: https://arxiv.org/abs/2004.12801
and it feels that it should have an easy proof for all $k$, but I don't see it.