Fano planes probability

Question

I have to find the threshold probability for containing a Fano plane. Since its a 3-hypergraph with 7 vertices and 7 hyperedges I was following the same approach as in:

https://math.stackexchange.com/a/4073729/874698

I have a small doubt here: since the Fano plane has a particular shape, thus, when calculating the variance, I believe we should get only the following cases

(i) no two Fano planes share a hyperedge

(ii) two Fano planes share one hyperedge

(iii) two Fano planes share all 7 hyperedges, i.e. they are the same.

Essentially, I think it is not possible for two Fano planes to share two or more hyperedges. Is it correct? Or its shape can be distorted so as to only keep the essential structure? Thanks in advance.

Answer 1

A quick way to check this theory is to ask: how many hyperedges are left in the Fano plane if we delete one vertex? (Doesn't matter which one; the Fano plane is very symmetric.)

We still have $4$ edges.

So it's possible for two Fano planes to intersect and share $6$ of their vertices and $4$ of their edges.

What if we delete $2$ vertices? You should be able to convince yourself with a similar diagram that $2$ edges are always left. (Again, this happens no matter which two vertices you delete - there's a high degree of symmetry.) So it's possible for two Fano planes to intersect and share $5$ of their vertices and $2$ of their edges.

If we delete $3$ vertices, we are left with either $0$ or $1$ edges. So it seems like we should consider the case where two Fano planes share $4$ of their vertices and $1$ of their edges. But no - at that point, if the Fano planes share only $1$ edge, we might as well assume that they share only the $3$ vertices in that edge.

Finally, if two Fano planes share fewer than $3$ vertices, they can't share any edges - so the dominant term of this form comes from Fano planes that share no vertices.

---

You might ask: what's the general strategy for making sure we don't miss all the cases?

Well, we don't have to get all the cases. We just have to make sure that we consider the leading cases: the most efficient ways to intersect. So far, we've found intersections with

• $0$ common vertices, $0$ common edges
• $3$ common vertices, $1$ common edge
• $5$ common vertices, $2$ common edges
• $6$ common vertices, $4$ common edges
• $7$ common vertices, $7$ common edges

and we can prove that any other situation is dominated by one of these: it either has the same number of common vertices and fewer common edges, or the same number of common edges but more common vertices, or is worse on both counts. That's how we tell, because sharing $x$ common vertices and $y$ common edges gives an $O(n^{2\cdot7 - x} p^{2\cdot7-y})$ term, and $p \to 0$ as $n \to \infty$.

More advanced technique is possible. Once we know the threshold $p = n^{-\alpha}$, we can compare terms by their behavior at that threshold! This comes down to comparing the density of a graph or hypergraph (the density is $\frac{\text{# edges}}{\text{# vertices}}$) to the density of its subgraphs. As long as you don't find any subgraphs with higher density than the entire graph, the variance method should work.

Answer 2

To find the threshold probability for containing a Fano Plane we use the idea from Theorem on density of hypergraph(H) The density is $ \rho(H) = \frac{ | E(H) | }{| V(H) |}$ and if this condition holds $\rho^{\max(H)} = \max_{F \subseteq H} \rho(F) $ then Then the threshold probability can be gotten as $n^{-\frac{1}{ \rho^{\max(H)}}}$

So applying the theorem on the Fano graph where:

$|E(H)| = 6+6+3 =15$

$|V(H)| = 7$ and $\rho(H) = \frac{15}{7} = 2.143$

Let $H = $ Fana plane. From theorem above $H$'s enough to find $ \rho^{\max(H)}$. Looking at any $F \subset H$. Using some cases on number of vertices of $F$:

Case 1: If we remove 1-vertex $ \left( V(F) \leq 5 \right), \rho(F) \leq \frac{15-3}{7-3} = \frac{12}{6} = 2$

Case 2: If we remove 2-vertices $ \left( V(F) \leq 4 \right), \rho(F) = \frac{9}{5} < 2$

Continuing in this manner shows that our graph is strictly balance since $ \rho^{\max }(H) = \rho{(H) }$

Therefore the threshold probability is $n^{- \frac{1}{\frac{15}{7} }} = n^{- \frac{7}{15}}$