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