NHacker Next
  • new
  • past
  • show
  • ask
  • show
  • jobs
  • submit
▲Dirac's Theorem at a Dinner Party (prideout.net)
SamBam 16 minutes ago [-]
> A Hamiltonian cycle is a way to seat everyone at a round table so that each guest sits between two friends.

My mother, from a very WASPy family, would have hated a Hamiltonian cycle dinner party. She always sat couples and close friends apart, in order to stimulate the conversation. Now that I'm the adult, I don't dictate who sits where, but there is a small, judgy part of me that still cringes a little if a couple insists on sitting together.

I wonder if there's a similar theorem for an anti-Hamiltonian cycle. One where as few close connections as possible sit together.

Actually, as a middle school teacher who is always tweaking the seating plan to try and improve classroom management, that's not far from what I already do. (Must be shades of my mother in me.)

jonahx 1 hours ago [-]
This is really nicely done.

The visualizations make the "flip" part of the argument immediately clear.

For the potato part, for me, an abstract verbal argument is clearer:

For any gap (u,v), mark all v neighbors, and all clockwise successors of all u neighbors.

n marks are now distributed among n-1 vertices (since v can't be marked). By pigeonhole, some vertex has 2 marks.

pepy07 1 hours ago [-]
This is a really clever way of demonstrating Dirac's theorem.
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact
Rendered at 21:22:12 GMT+0000 (Coordinated Universal Time) with Vercel.