# Number of three-element sets with all three two-element subsets with a property, given the number of two-element sets with that property.

Consider a set $$A$$ with $$|A|=n \ge 3$$, the set $$A_2 = \{\{a,b\} : a,b \in A\}$$, the set $$A_3 = \{\{a,b,c\} : a,b,c \in A\}$$, a function $$f: A_2 \to \{0,1\}$$ and the set $$C_2 = \{\{a,b\} : {a,b \in A} \land {f(\{a,b\}) = 1}\}$$.

Suppose we know that $$|C_2| \ge q|A_2| = q{n \choose 2}$$, $$0 \lt q \le 1$$.

Now let $$C_3 = \{\{a,b,c\} : {a,b,c \in A} \land {f(\{a,b\}) = 1} \land {f(\{a,c\}) = 1} \land {f(\{b,c\}) = 1}\}$$.

Is it always true that:

$$|C_3| \ge q^3|A_3| = q^3{n \choose 3}?$$

I am a little doubtful because $$\{a,b\}$$, $$\{a,c\}$$ and $$\{b,c\}$$ don't look fully independent because they share one element between themselves.

• Do you really mean $A_2 = \{ \{a,b\} \mid a,b \in A \}$, or do you mean that $A_2$ is the set of 2-element subsets of $A$ as you say in the title? These are not quite the same… Oct 3 at 15:54
• @PeterLeFanuLumsdaine How are they different? Oct 3 at 16:08
• @Vincent: $\{ \{a,b\} \mid a\in A\}$ doesn’t specify that $a$ and $b$ must be distinct, so it also includes singletons $\{x,x\} = \{x\}$. Oct 3 at 16:23
• Well, I am not a mathematician, but I thought $a \not = b$ is implicit in the set notation $\{a,b\}$. Anyway this is what I mean. I might make it explicit if needed. Oct 3 at 18:08
• @BillyJoe: In some contexts, yes, people write things like “Take some set $\{a,b\}$” and implicitly mean $a,b$ to be distinct. I think most would consider that a little sloppy, or informal at best. But distinctness is never be taken as implicit in a set-forming operation like $\{ \underline{\qquad} \mid a,b \in A \}$ — there, like in a quantification “for all $a, b \in A$”, it’s unambiguous that it ranges over all $a,b$ satisfying the constraints explicitly given. Oct 3 at 21:23

To put it more visually: suppose you have a graph in which at least a fraction $$q$$ of pairs of vertices are connected by an edge, or equivalently: in which at least a fraction $$q$$ of possible edges actually exist. Your question is then if at least a fraction $$q^3$$ of possible triangles must exist as well.
Put like this it seems fairly obvious that the answer is no: it is easy to imagine a graph with a non-zero number of edges (and hence non-zero $$q$$) but no triangles at all.
(Caveat: this sort of assumes you are talking about all $$n$$ and all $$q$$ chosen in whatever order you like. My simple argument does not rule out a version of your claim starting with: 'For every $$q \in (0, 1)$$ there is an $$N$$ such that for all $$n > N$$...'. I'm not sure if some statement like that could be true or not.)