Re: [math-fun] Maximum number of triples of orthogonal directions
WDS: Allan Wechsler sent me various confused emails, but eventually unconfused himself, with the result his construction showing f(8)>=4, is now declared broken. My use of it to try to show f(n+6) >= 4+f(n) is similarly declared broken.
AW:: Taking a deep breath and trying again. I think my eight-direction configuration is not, in fact, realizable. The trouble is that AC, CE, EG, GA are all orthogonal pairs. I don't think that this spherical quadrilateral actually can flex in the way that we imagined. It can "fold", but one of the pairs AE, CG must remain antipodal. This forces identifications, so that the whole thing is reduced to the "bow-tie" configuration of five points we identified earlier, PQR+RST.
--WDS: Aha. The "flexible quadrilateral" ACEG... has a problem. If fix A at North pole of sphere of directions, then C,G both must be on equator no matter how you flex, which means E must be at either North or South pole no matter how you flex. Which means you lose, since A and E then represent the same direction, which is forbidden. It's kind of strange: essentially any spherical quadrilateral is flexible, but for this particular one, it has this miraculous sort of semi-rigid property. --However, to now make lemonade from lemons, this tells us that the 4-cycle is a forbidden subgraph, leading to stronger upper bounds. Specifically, an upper bound U on f(N) is: the most triangles any N-vertex graph G can have, where only graphs G not containing a 4-cycle, are allowed. On this topic, see http://arxiv.org/abs/1201.4912 which is about a different problem, but perhaps relevant.
Warren's description, 99% spot on, needs one minor footnote: E can avoid being at the south pole, but only if C and G are antipodal -- the important point being that we cannot avoid having at least one of the pairs AE, CG antipodal. The exclusion of the 4-cycle means that we don't have to treat <|> specially anymore: it's automatically excluded since it has a 4-cycle in it. I once considered the problem of maximizing the number of edges in the same class of graphs, and blogged about it starting here: http://acw.livejournal.com/61151.html, and continuing over several posts shortly thereafter. The punchline was that after I accumulated enough data, OEIS told me that the problem had been considered before, and that such graphs were called *squarefree*: see http://oeis.org/A006855 for more details. As far as I know, the constraint that the graph be realizable as the orthogonalities of a set of lines through the origin in 3-space is original to Warren, as is his focus on counting triangles rather than edges. (Edge-rich graphs, of course, *tend* to have lots of triangles, and I would expect some of the extremal examples to be identical. I have lost track: do we yet have an example of a squarefree graph that is *not* realizable? I'm no longer confident of my conjecture, even weakened to the squarefree case rather than the <|>-free case. On Fri, Jan 31, 2014 at 5:23 PM, Warren D Smith <warren.wds@gmail.com>wrote:
WDS: Allan Wechsler sent me various confused emails, but eventually unconfused himself, with the result his construction showing f(8)>=4, is now declared broken. My use of it to try to show f(n+6) >= 4+f(n) is similarly declared broken.
AW:: Taking a deep breath and trying again. I think my eight-direction configuration is not, in fact, realizable. The trouble is that AC, CE, EG, GA are all orthogonal pairs. I don't think that this spherical quadrilateral actually can flex in the way that we imagined. It can "fold", but one of the pairs AE, CG must remain antipodal. This forces identifications, so that the whole thing is reduced to the "bow-tie" configuration of five points we identified earlier, PQR+RST.
--WDS: Aha. The "flexible quadrilateral" ACEG... has a problem. If fix A at North pole of sphere of directions, then C,G both must be on equator no matter how you flex, which means E must be at either North or South pole no matter how you flex.
Which means you lose, since A and E then represent the same direction, which is forbidden. It's kind of strange: essentially any spherical quadrilateral is flexible, but for this particular one, it has this miraculous sort of semi-rigid property.
--However, to now make lemonade from lemons, this tells us that the 4-cycle is a forbidden subgraph, leading to stronger upper bounds.
Specifically, an upper bound U on f(N) is: the most triangles any N-vertex graph G can have, where only graphs G not containing a 4-cycle, are allowed. On this topic, see http://arxiv.org/abs/1201.4912 which is about a different problem, but perhaps relevant.
I have no confidence at all that every squarefree graph is realizable. In fact, I can actually disprove this, except my disproof currently cheats slightly. Namely, the two papers I cited before show that maximal squarefree graph has order V^(3/2) edges, whereas unit-distance graph has O(V^(4/3)) edges, hence not every squarefree graph is realizable as a unit distance graph, QED. The reasons this "cheated" is I never verified the Szekely paper's V^(4/3) bound works on spheres. But aside from that, this seems solid. So anyhow, the squarefree graph thing merely yields an upper bound on f(N). But you can for any particular N work out f(N) by machine by considering every possible N-vertex graph and deciding if it is realizable. It ain't an easy job, but it is doable in principle. In fact you can probably get up to maybe N=10 just manually. We don't need no stinking computers, real men cut triangular thingummies with their bowie knives and move them around on spheres to solve such things. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
And real women (like my wife, who is a lurker on this forum) design origami modules and link them together to investigate similar things. I will try to think more about this over the weekend; maybe we can get enough terms to search OEIS. Thank you for an enjoyable problem, Warren. On Fri, Jan 31, 2014 at 6:47 PM, Warren D Smith <warren.wds@gmail.com>wrote:
I have no confidence at all that every squarefree graph is realizable.
In fact, I can actually disprove this, except my disproof currently cheats slightly. Namely, the two papers I cited before show that maximal squarefree graph has order V^(3/2) edges, whereas unit-distance graph has O(V^(4/3)) edges, hence not every squarefree graph is realizable as a unit distance graph, QED. The reasons this "cheated" is I never verified the Szekely paper's V^(4/3) bound works on spheres. But aside from that, this seems solid.
So anyhow, the squarefree graph thing merely yields an upper bound on f(N).
But you can for any particular N work out f(N) by machine by considering every possible N-vertex graph and deciding if it is realizable. It ain't an easy job, but it is doable in principle. In fact you can probably get up to maybe N=10 just manually. We don't need no stinking computers, real men cut triangular thingummies with their bowie knives and move them around on spheres to solve such things.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (2)
-
Allan Wechsler -
Warren D Smith