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.

  • $\begingroup$ 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… $\endgroup$ Oct 3 at 15:54
  • $\begingroup$ @PeterLeFanuLumsdaine How are they different? $\endgroup$
    – Vincent
    Oct 3 at 16:08
  • $\begingroup$ @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\}$. $\endgroup$ Oct 3 at 16:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – BillyJoe
    Oct 3 at 18:08
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 3 at 21:23

1 Answer 1


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.