Re: [math-fun] Maximum number of triples of orthogonal directions
f(8) is at least 4, because ABC+CDE+EFG+GHA can be realized. I don't think it would be too much work to show that 5 is not possible. 1,1,2,2,3,4, unsurprisingly, has hundreds of hits on OEIS, so we need more terms. I have a suspicion that all the graphs of the class you describe (no four vertices with a "lune", AB+AC+BC+BD+CD) are "realizable" as orthogonality graphs in the projective plane. If they are different, then your function f probably won't diverge from the corresponding Ramsey Theory question (largest number of triangles in a luneless graph) for quite a while. We should think about trying to prove the realizability conjecture. I have only the very vaguest inklings about how to try that. On Thu, Jan 30, 2014 at 8:35 PM, Warren D Smith <warren.wds@gmail.com>wrote:
I posted this to math-fun also, but it has not been "approved" yet by RCS:
I can prove f(6)=2 and f(7)=3.
An upper bound on F(n) which shows this is: the maximum number of triangles in an n-vertex graph G, where only G which do not contain <|> as a 4-vertex subgraph, are allowed.
This function of n is also interesting by itself, and I do not know what it is.
On 1/30/14, Allan Wechsler <acwacw@gmail.com> wrote:
f(8) is at least 4, because ABC+CDE+EFG+GHA can be realized.
--I agree. This same argument would seem to show an infinite set of lower bounds. I'm not sure what the best would be, but certainly it ought to show f(2*n) >= n for each n>=2 by realizing a "necklace of triangles." That improves on my lower bound only in the case 2*n=8, however!
I have a suspicion that all the graphs of the class you describe (no four vertices with a "lune", AB+AC+BC+BD+CD) are "realizable" as orthogonality graphs in the projective plane. If they are different, then your function f probably won't diverge from the corresponding Ramsey Theory question (largest number of triangles in a luneless graph) for quite a while. We should think about trying to prove the realizability conjecture. I have only the very vaguest inklings about how to try that.
--that is a bold conjecture. I would suggest to you that what is likely to be a critical case for this conjecture is the graph of the cuboctahedron http://en.wikipedia.org/wiki/Cuboctahedron which (according to this conjecture) would be realizable to show f(12)>=8, presumably then with equality. Or it is likely to refute the conjecture. As they say on Fox News, "We report. You decide." :) Meanwhile here is the latest evolving table of lower & upper bounds, *s placed after entries that improved: N=3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 L=1 1 2 2 3 4* 4 5 5 6 7* 7 8 9 10*10 11 11 12 13 14 14 15 16* 16 17 18 18 19 19 U=1 1 2 2*3*8 12 13 17 20 26 28 35 37 44 48 57 60 70 73 83 88 100 104 117 121 134 140 155 160
The Wechsler conjecture would show f(9)>=6 should be achievable by connecting 6 triangles via shared vertices in a K33 connection pattern (each red triangle shares each vertex with exactly 1 blue triangle). However, I doubt it. I think this configuration cannot be realized and if so the Wechsler conjecture is disproven. On the bright side, every time you find another unrealizable configuration, you can add that as a new excluded subgraph making the combinatorial upper bound get tighter. [Also, by using Petersen graph instead of K33 we would find f(15)>=10.
From Heawood graph we would find f(21)>=14. From Tutte-Coxeter graph would follow f(45)>=30. Some of these might even be true.]
Perhaps relevant: This paper by LA Szekely http://www.cs.umd.edu/~gasarch/erdos_dist/szekely.pdf proves that a V-vertex graph drawn in the plane with line segment edges, each of length=1, has at most O(V^(4/3)) edges. I think (have not checked carefully!) his proof also is valid for graphs drawn on surface of a sphere using geodesic segment edges. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The following theorems are easy (n>1 assumed in them all): 1: f(n+1) >= f(n) 2: f(2*n-1) >= 2*f(n) 3: f(n+5) >= 3+f(n) 4: f(n+2) >= 1+f(n) PROOFS: 1: just add a new direction and don't use it. 2: take an n-direction configuration twice, and rotate the 2nd configuration around until it shares a point with the 1st. 3: Like Wechsler's proof f(8)>=4 (which is a special case of this); essentially you adjoin |> |> |> to an n-configuration and make the two furthest apart points of the adjoined thing, coincide with old points. 4: Adjoin |> but make one of the new points coincide with an old point. Q.E.D. Application: My cruddy search hack found f(27)>=17 and then applying (3) we deduce f(32)>=20. CONJECTURE: |2*f(n) - 3*n| remains bounded by some constant independent of n. This conjecture arises by counting degrees of freedom D and counting constraining equations E, and hoping that a solution never exists if E>=D+SuitableConstant, but always exists if D>=E+SuitableConstant. Here is the latest table of bounds (where * suffix is improvement): N=3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 L=1 1 2 2 3 4* 4 5 5 6 7* 7 8 9 10*10 11 11 13*13 14 14 15 16* 17* 17 18 18 19 20* U=1 1 2 2*3*8 12 13 17 20 26 28 35 37 44 48 57 60 70 73 83 88 100 104 117 121 134 140 155 160
The following theorems are easy (n>1 assumed in them all):... 2: f(2*n-1) >= 2*f(n)
--more generally by the same reasoning, f(a+b-1) >= f(a)+f(b). --I further conjecture that f(n+6)>=4+f(n) if n>3. I almost have a proof. Observe that Wechlser's configuration ABC+CDE+EFG+GHA showing f(8)>=4 is flexible, the angle between A and E can be flexed to become any value between 0 and 180 degrees (except 90). So we adjoin Wechsler's configuration to f(n) flexing and rotating it until A and E coincide with two old non-orthogonal directions in the f(n) configuration. This would prove it, except for the annoying possibility that another of the added directions would coincide with an old one causing a screw-up similar in nature to the forbidden 90-degree AE flex. I presume that fate can usually or always be avoided if n>3, but do not have a proof. Anyhow, assuming this is true, would establish the lower bound on f(n) half of my conjecture that |2f-3n| stays bounded.
I am experiencing some anxiety about the configuration you named after me. I fear that it's simply half of a flexing cuboctohedron, and therefore that B and F are collinear in all positions (as are D and H). But I don't know if I should be upset about it ... doesn't that mean that we have achieved four triples on only six directions? Wait a minute ... we proved that impossible. Now I'm all confused. On Fri, Jan 31, 2014 at 1:06 PM, Warren D Smith <warren.wds@gmail.com>wrote:
The following theorems are easy (n>1 assumed in them all):... 2: f(2*n-1) >= 2*f(n)
--more generally by the same reasoning, f(a+b-1) >= f(a)+f(b).
--I further conjecture that f(n+6)>=4+f(n) if n>3. I almost have a proof. Observe that Wechlser's configuration ABC+CDE+EFG+GHA showing f(8)>=4 is flexible, the angle between A and E can be flexed to become any value between 0 and 180 degrees (except 90). So we adjoin Wechsler's configuration to f(n) flexing and rotating it until A and E coincide with two old non-orthogonal directions in the f(n) configuration. This would prove it, except for the annoying possibility that another of the added directions would coincide with an old one causing a screw-up similar in nature to the forbidden 90-degree AE flex. I presume that fate can usually or always be avoided if n>3, but do not have a proof.
Anyhow, assuming this is true, would establish the lower bound on f(n) half of my conjecture that |2f-3n| stays bounded.
This paper by LA Szekely http://www.cs.umd.edu/~gasarch/erdos_dist/szekely.pdf proves that a V-vertex graph drawn in the plane with line segment edges, each of length=1, has at most O(V^(4/3)) edges. I think (have not checked carefully!) his proof also is valid for graphs drawn on surface of a sphere using geodesic segment edges.
--I now checked carefully. It actually is quite amazing how Szekely gets all these cool results without using anything other than the notion of "crossing number in a plane topology" which of course works on a sphere too since they have same topology. So anyhow, as (yet another) consequence, as explained last post, we now know that: not every squarefree graph is realizable.
Just using floor( http://oeis.org/A006855 / 3 ) gives an upper bound on f(N).
From it we find
f(3)=1, f(4)=1, f(5)=2, f(6)=2, f(7)=3, f(8)=3, f(9)=4, f(10)=5. The first open case now is f(11)=5 or 6. [If the graph G arising from the Petersen graph P by using vertices(G)=EdgeMidpoints(P) and draw a G-triangle for each P-vertex, is realizable, that would prove f(15)=10.] -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The first open case now is f(11)=5 or 6.
--And it is: f(11)=5. [Because you can see there can be at most 1 cycle in the hypergraph, hyperedges being triangles.] Now first open case is f(12)=6 or 7, and I think the same argument shows it is 6. So then the sequence begins 1,1,2,2,3,3,4,5,5,6 which gets 16 hits on oeis.org. Of those 16, I believe none have any hope of being the answer.
Since more results keep coming, I've made a manuscript which you can read here summarizing them: https://dl.dropboxusercontent.com/u/3507527/OrthogTriads.html
Typo at "Suspicion"; you say you suspect f(14)=18, but I'm pretty sure you meant 8. Interesting work. On Sat, Feb 1, 2014 at 2:48 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Since more results keep coming, I've made a manuscript which you can read here summarizing them: https://dl.dropboxusercontent.com/u/3507527/OrthogTriads.html
participants (2)
-
Allan Wechsler -
Warren D Smith