Comment by zasdffaa | Hacker News Reader

Comment by zasdffaa | Hacker News Reader

Parent Full thread

I get creative, but comprehensibility eludes me. To some https://www.cs.stanford.edu/~knuth/papers/huang.pdf may be obvious in its statements and steps and I guess that, aside from having the necessary background in this area, they fundamentally differ from me in how they 'see' this. They the underlying meaning, to me it's a jungle.

Take the statement of the problem

??? ??? ? ?? ? ??? / ? ???????? ?? ??? ????? ? ???????? ? ?????? ???? ?? ????? ? ? ?????? ??? ?? ?

ok, so you can't C&P from that PDF :) by hand then: "Any set H of 2^(n-1) + 1 vertices of the n-cube contains a vertex with at least sqrt(n) neighbors in H"

Nothing in that makes intuitive sense to me except vertices will have neighbouring vertices. It's not even dimension limited and I can just about manage 4 dimensions at a push.

Next, a bunch of recursively defined 2x2 matrices with no apparent link to anything. I'm lost twice now. Yet to a Knuth or a Von Neumann, it just makes sense. This stuff makes me feel like a different species.

Just a reflection on things. Professional mathematicians in-chimings welcome.

the combinatorial object "the n-cube" is just length n bitstrings, neighbor means one bit flip away. It can be thought of as being embedded in the geometric n cube.

the recursive matrices as they are defined are, if you ignore the signs, the incidence matrices of the n cubes. This is only mentioned in the final line of the paper (which is not totally unreasonable). The rest of the result is just some pretty basic facts in linear algebra, but you still have to be comfortable with linear algebra in order to see why they might be natural constructions.

How is the bitstring 'embedded' in the n-cube? It must be a linearisation from a 1-dimensional string to vertices of the n-dimensional object but...? What does 'embedded' even mean, mathematically.

Edit: neighbouring vertices can't be collapsed to a 1-dim string such that each bit x in the string abuts bit y if x is a neighbouring vertex of y (neighbouring = 1 edge away). Works for 1 and 2 dim cubes (line and square) fails for 3. Maybe am missing something.

'incidence matrices' something is incident on something else? It occurs to me that in some sense the recursive matrices might represent the n-cube, each sub-matrix being an n-1 cube. If this is so it is starting to make a little sense.

But that's not the point, which is, how are you seeing this so clearly? It's like a pea-souper over at my end.

(https://en.wikipedia.org/wiki/Pea_soup_fog)

> Edit: neighbouring vertices can't be collapsed to a 1-dim string such that each bit x in the string abuts bit y if x is a neighbouring vertex of y (neighbouring = 1 edge away). Works for 1 and 2 dim cubes (line and square) fails for 3. Maybe am missing something.

It sounds like you're missing something. A 3-dimensional cube has 2^3 = 8 vertices:

Since there are three dimensions, each vertex has three neighbors. If you imagine the vertex at (0, 1, 1), you can travel across the x-dimension to the neighbor at (1, 1, 1), or across the y-dimension to the neighbor at (0, 0, 1), or across the z-dimension to the neighbor at (0, 1, 0). Obviously, you represent this by flipping the x-, y-, or z-bit in the corresponding bitstring representation. The bitstring representation itself is blindingly straightforward: the vertex at (0, 1, 1) has the representation 011, etc.

It's not really clear to me where you're becoming confused?

> What does 'embedded' even mean, mathematically.

In this case, it means that a complex structure (the cube) includes a simpler structure (the collection of discrete bitstrings). You can analyze the bitstrings by themselves if you want to, or you can imagine them as being the vertices of a cube that may or may not have properties other than its vertices, but however you describe the cube, it will include the bitstrings.

> It's not really clear to me where you're becoming confused?

Got it. I was interpreting the bitstring as 1 bit mapped to each vertex of the cube, I so badly, utterly misinterpreted it (my string would be 2^n length, not n-length). A simple example and the intent here is totally clear. I guess the problem is at least partly I tend to read what I expect, not what's there. Sigh.

> In this case, it means that a complex structure (the cube) includes....

Righto, a model of interest, a *-morphism or bijection between the string-set and the cube (where * = iso/homo/auto/whatever, it's been a long time)

Thanks for this.

Reply on news.ycombinator.com