2
$\begingroup$

Motivation. Today my sons played a card game, in which a fixed number $n$ of cards was lying on the table. A move consists of adding an unused card to the cards on the table, and removing a card from the table, so that after the move, there are again $n$ cards on the table. Which made me ponder the following question.

Formalization. For any integer $n>1$ let $[\mathbb{N}]^n$ be the collection of subsets of $\mathbb{N}$ consisting of $n$ elements. For which integers $n>1$ is there a bijection $\varphi:\mathbb{N}\to [\mathbb{N}]^n$ such that for all $k\in\mathbb{N}$ we have $|\varphi(k) \cap \varphi(k+1)| = n-1$?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The famous Johnson graph $J(n,k)$ (en.wikipedia.org/wiki/Johnson_graph) is the graph whose vertices are $k$-subsets of $[n] = \{1,\ldots,n\}$, with an edge between vertices if their intersection has size $k-1$. You are asking about the analogous graph "$J(\infty,k)$," where the subsets are now of $\mathbb{N}$ instead of $[n]$. Specifically, you are asking whether this $J(\infty,k)$ has a Hamiltonian path. For comparison, it is known that all the $J(n,k)$ have Hamiltonian paths (in fact, Hamiltonian cycles). Anyways, this doesn't answer your question, but may be a starting point. $\endgroup$
    – Sam Hopkins
    Commented Apr 30, 2023 at 20:20

1 Answer 1

Reset to default
7
$\begingroup$

$[\mathbb{N}]^n$, with edges between $a,b\in[\mathbb{N}]^n$ if $\#(a\cap b)=n-1$, is an infinite graph in which all vertices have infinite degree. Moreover, for any two vertices $a,b$ in $[\mathbb{N}]^n$ and any finite subset $E\subseteq[\mathbb{N}]^n$ not containing $a,b$, there is a path from $a$ to $b$ which does not pass through any vertices of $E$: to find it, one can consider some $N\in\mathbb{N}$ bigger than all natural numbers appearing in elements of $E$, and then you go from $a$ to $\{N+1,\dots,N+n\}$ and from $\{N+1,\dots,N+n\}$ to $b$ in $\leq 2n$ steps.

So one can create a Hamiltonian path in the following way:

  • Number the vertices $u_1,u_2,\dots$ in $[\mathbb{N}]^n$.

  • Start the path in the vertex $u_1$.

  • At each step, take the first vertex that you have not visited and visit it using a path that does not pass through any previously visited vertices.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .