With regards to the fine intersection problem for Steiner triple systems, I can now prove that |I(v)| = Θ(v³).
The intersection of two Steiner triple systems (X, A) and (X, B) is the set A∩B. The fine intersection problem for Steiner triple systems asks to determine for each v, the set I(v), consisting of all possible pairs (m, n) such that there exist two Steiner triple systems of order v whose intersection I satisfies |∪(A∈I)| = m and |I| = n. It is easy to show that |I(v)| ≤ v³/18 + o(v³). Previous results only establish that |I(v)| ≥ v²/6 + o(v²). I conjecture that |I(v)| = v³/18 + o(v³). I'm currently trying to prove that |I(v)| = Θ(v³).
Jan K. Haugland has created a nice site on grid subgraphs with large girths.
Jan K. Haugland proved that f(4) = 3/8 recently. We also managed to show now that lim f(d+1)/f(d) = 1.
A result of Lazebnik and Ustimenko can be used to show that f(d) > Alog(d)/d.
With respect to the problem described, Jan Haugland and I have been corresponding a little bit. We managed to show that 2/(f(d)+2) <= f(d+1)/f(d) < 1 for all d. We think lim f(d+1)/f(d) exists. This follows if lim f(d) = 0, which we presume would not be too difficult to resolve. Jan thinks f(d) grows roughly like Alog(d)/d.
Considering planar graphs embedded on a sphere, we see that g(d+2) <= 2e by going through all the faces. This inequality gives f(d) >= 2/(d+2). The following construction gives a better bound on f(d).
Given d, let n be the smallest prime power such that d <= n^3-1. Now take a projective plane of order n and consider its point-block incidence graph G. G has v = 2(n^2+n+1) vertices, e = (n+1)(n^2+n+1) edges, and girth 6. Now, e-v = n^3-1 >= d. Since f is a decreasing function, we now have f(d) > 6/((n+1)(n^2+n+1)) = (6/d)*(1-2/(n+1)) = (6/d)*(1-2/(d^(1/3)+1)).
On 17 Jan 2003, Jan Kristian Haugland posted the following interesting problem on sci.math.research.
For a graph G, let d(G) = |E(G)|-|V(G)| and define
He observed that:
i) f(d) = 0 for d < 0;
ii) f(0) = 1;
iii) f(1) = 2/3;
iv) f(2) = 1/2;
and asked if f(3) = 4/9 (as achieved by K_3,3) and f(5) = 1/3 (as achieved by the Petersen graph).
I can show that 2f(d)/3 <= f(d+1) <= f(d). When I have time, I will investigate this problem further.