I did exactly that. Some say induction works, others say inequalities for independent sets work. idk really

What is the difficulty of this problem in terms of ISL?

Maybe the method used in the proof of Turan theorem can help in this problem. I mean copy a vertex and delete another (which isn't its neighbor)to get a better graph.

Hint: (Also Junior KMO #8) Say there are $n$ students, and the maximal complete subgraph's size is no more than $k$. The number of complete subgraph is no more than $3^{\frac{n+k}{3}}$. This can solve the problem, as we replace $n$ with $2n$ and $k$ with $n$. This can be proved by induction over $n+k$.

An interesting solution is to prove that if there are $n$ students, and the maximum number of students in a well-formed set is no more than $k$($k\leq n$), the number of well-formed sets are less than or equal to $2^{2k-n}3^{n-k}$. It can be easily proved by induction on $(k,n)$ in lexicographical order.

Solved with clowns and moral support from william122 Call the graph we are working with $\mathcal G$. We claim that the maximum is $\boxed{3^n}$ which can be done by choosing the complement of $\mathcal G$ to be a matching. Definition [Vertex Clowning]: Define a clown of a vertex $u$ to be a vertex having the same neighborhood as $u$ but not adjacent to $u$. Definition [Stability under clowning]: We say that a vertex $x$ is stable if in the complementary graph $\overline{\mathcal G}$, $x$ belong to some clique that is disconnected from the rest of the graph. Note that if $x$ is stable then it cannot be used to clown other vertices, and it cannot be clowned by another vertex. Moreover, when one vertex clowns another, adjacency relations to $x$ are unchanged. Part 1: Clowning for as long as possible Let $f(u)$ denote the number of cliques containing $u$. First choose $$u \in \arg\max_{x \text{ not stable}} f(x)$$and in each step (when possible), choose $v \not \sim u$ such that $v$ is not a clown of $u$, then replace $v$ by a clown of $u$. Moreover, after clowning we draw a red edge between those pairs of clowns of $u$ ($u$ itself included) that have not received a red edge between them, unless there is some new vertex $x$ not stable with $f(x) > f(u) = f(v)$ caused by the clowning, in which case we erase all red edges and restart the process with $x$ instead of $u$. Remark that There are no $n+1$-cliques: If a new $n+1$-clique is created, it can use exactly one of $u,v$. Note that $u \cup K_n$ is an $n+1$-clique if and only if $v\cup K_n$ is because now $v$ is a clown of $u$. Now before $v$ became a clown of $u$, this $u\cup K_n$ should still exist since $v\not \in K_n$ as $v\not \sim u$, contradiction to the assumption that there are no $K_{n+1}$'s. The number of cliques in the graph does not increase, because in the clowning process all $f(v)$ cliques originally containing $v$ were removed, and then $f(u) \ge f(v)$ containing $v$ were created. All other cliques were left unchanged. $v_1v_2, v_1v_3$ are both red edges, then so is $v_2v_3$. Note that after each time we erase some red edges, $\arg \max_{x \text{ not stable}} f(x)$ increases, but this is bounded above, so we can only erase finitely many times. Suppose we are at a point where no more erasing of red edges occur. Each step increases the number of clowns of $u$ by $1$, so the process terminates after some time with red edges forming a clique that is separate from the rest of the graph in the complementary graph of $\mathcal G$, and all vertices in the red clique become stable. We repeat the above operation until it cannot be done. Part 2: Algebra The complementary graph of the resulting $\mathcal G$ is a union of pairwise disconnected cliques of sizes $n_1\ge \dots \ge n_k > \underbrace{1,\dots, 1}_{s \text{ copies}}$. The number of cliques in $\mathcal G$ is $$2^s \prod_{i=1}^k (n_i+1) \le 2^s \cdot \frac{(\sum n_i + k)^k}{k^k} = \frac{2^s(2n-s+k)^k}{k^k}$$with $\sum_{i=1}^k n_i = 2n-s$ and $k+s \le n$. First we show that $s = n-k$ when the maximum of the RHS is reached. For $k+s \le n-1$, Note that $$\frac{2^{s+1}(2n-s-1+k)^k}{2^s(2n-s+k)^k} > 1$$follows from $\frac{(2n-s+k)^k}{(2n-s-1+k)^k} = (1+\frac{1}{2n-s-1+k})^k \le (1+\frac{1}{2k})^k <\sqrt{e} < 2$. Now it suffices to maximize $$\frac{2^{n}(n+2k)^k}{(2k)^k}$$since the function $(1+\frac{a}{x})^x$ is increasing for any $a > 1$ the maximum of the above as a function of $k$ is reached when $k = n$, whence the quantity takes the value of $3^n$, as desired. $\blacksquare$

I have 2 questions about stroller's proof. First, I don't understand how a stable vertex $x$ cannot be a clown for another vertex because if you take a biparite graph like say $G=K_{2,3}$ and consider it's complement graph just because $A$ and $B$ the fact that $A$ and $B$ belong to a clique disconnected from the rest of the graph in the complement graph of $G$ implies that they are clowns of each other. Also, what does $u \in \arg\max_{x \text{ not stable}} f(x)$ mean? @below nice solution Edit: still nice

MarkBcc168 wrote: If $|N(S)|<|S|$, then $(\mathcal{A}\setminus N(S))\cup S$ had to be a clique in $G$. What if vertices in $S$ don't form a clique in $G$? For example, when $n=2$, let edges in $G$ be $A_1A_2,A_1B_1,A_1B_2$. Then there isn't a perfect matching in $\overline{G}$.

Plops wrote: I have 2 questions about stroller's proof.[...] Re 1st question: I said that if $x$ is stable then it cannot be used to clown other vertices (in fact every vertex in the clique of the complementary graph containing $x$ is a clown of $x$). clown wrote: Note that if $x$ is stable then it cannot be used to clown other vertices, and it cannot be clowned by another vertex. Moreover, when one vertex clowns another, adjacency relations to $x$ are unchanged. Here's more explanation for the first sentence. The key part in the definition of stable vertex is that the vertex is within some clique disconnected from the rest of the graph in the complementary graph of $\mathcal G$. What this means is that in $\mathcal G$, a stable vertex $x$ is contained in some independent set $I$ such that for any $v \in I$ and $w \not \in I$, $v$ is adjacent to $w$. In this case if $w \not \in I$ cannot clown $x$, nor can $x$ clown $w$, because $x$ and $w$ are adjacent. Do you like our clowning? For the 2nd question, well, we were clowning the other day so that $\text{arg}$ shouldn't be there in the $\text{arg} \max_{x\text{ not stable}} f(x)$ after the series of bullet points. It just means that each time we erase red edges means that the maximum of $f(x)$ over all unstable $x$ has increased and it cannot do so indefinitely. In Part 1 before the procession of bullet points, $\text{arg} \max_{x \text{ not stable}} f(x)$ has another appearance and it should be there. It means the set of vertices $x$ not stable that allows the function $f(x)$ to achieve maximum among the set of unstable vertices. It looks like clowning caused some confusions, but I had no other choice because I solved the problem with clowns. Please let me know if you have any more questions and thanks very much for reading this

Denote $G=(V,E)$ the graph. By Turan we can suppose $V=V_1+...+V_k,k\le n$ such that $G[V_i]$ are all independent. Then the number of cliques is $$\sum_{r}\sum_{1\le i_1 < i_2 < ... < i_n\le k} |V_{i_1}| |V_{i_2}|...|V_{i_r}| = \prod{(1+|V_i|)}\le (1+\frac{2n}{k})^k \le 3^n$$The equality holds when $k=n$ and $|V_1|=...=|V_n|=2$.

@above: in this manner you might run into a situation where after independent sets $V_1,.\dots,V_{i-1}$ are constructed, the remaining graph is a clique, so $|V_i| = \dots = |V_k| = 1$, in which case $k\le n$ might no longer hold. How do you ensure this doesn't happen?

something wrong

Could you please provide more details on how to apply Turan in this case? Thanks.

You are right. Turan doesn't work directly here.

Banana_17 wrote: You are right. Turan doesn't work directly here. When I was attempting this with clowns earlier, we tried to apply Turan but failed So I was just wondering if there'd be a nice way to apply Turan...

Turan's graph yields $3^n $ well-formed sets. Construction of Turan's graph Split the $2n $ students in $n $ pairs. A student knows everyone but the student with who he/she's paired. Since every complete subgraph (well-formed sets) has at most $n $ students. Pick a number $0\le k\le n (k\leqslant n)$ to find the number of well-formed sets. For that number we need to pick $k $ pairs within $n $ pairs. Then for each pair, pick a student. By Binomial theorem, it shows $= 3^n. $ Quote: Prove that if there are $n$ students, and the maximum number of students in a well-formed set is no more than $k$($k\leq n$), the number of well-formed sets are less than or equal to $2^{2k-n}3^{n-k}$. It can be easily proved by induction on $(k,n)$ in lexicographical order. If you have a Turan graph on $xn $ students such that well-formed sets have cardinality $\le n $ you'll have $ (x+1)^n $ well-formed sets.

The answer is \(3^n\), achieved by removing a perfect matching from \(K_{2n}\). First solution, by black magic (Luke Robitaille) We will show the following: In a graph if \(2n+m\) vertices, if there are no \(K_{n+m+1}\) then the number of cliques is at most \(3^n\cdot2^m\). Let \(f(n,m)\) be the maximum number of cliques. The case \(n=0\) is trivial. For \(n\ge1\), the graph is not a clique, so there is a vertex \(v\) that is not a universal vertex. It is not hard to check that the number of cliques without \(v\) is at most \(f(n-1,m+1)\), and the number of cliques with \(v\) is at most \(f(n-1,m)\). The conclusion follows inductively. Second solution, by generalized Tur\'an (Jeffrey Chen, et al.) I contend the number of \(K_i\) is at most \(2^i\binom ni\), which will suffice. This follows from the following claim: Claim: [General Tur\'an] If a graph on \(n\) vertices has no \(K_{r+1}\), then the number of \(K_k\) is at most \[\frac{(r-1)(r-2)\cdots(r-k+1)}{r^{k-1}}\cdot\frac{n^k}{k!}.\] Proof. Induction on \(n\): take a maximal graph \(G\), so \(G\) contains a \(K_r\). By taking cases on the number of vertices of each \(K_k\) are in the \(K_r\), we have \begin{align*} \#K_k&\le\frac{(r-1)\cdots(r-k+1)}{r^{k-1}}\cdot\frac{(n-r)^k}{k!} +\frac{r(r-1)\cdots(r-k+1)}{k!}\\ &\qquad +\sum_{i=1}^{k-1}\frac{(r-1)\cdots(r-i+1)}{r^{i-1}}\cdot\frac{(n-r)^i}{i!} \cdot\frac{(r-1)\cdots(r-k+i)}{(k-i)!}\\ &=\frac{(r-1)(r-2)\cdots(r-k+1)}{r^{k-1}}\cdot\frac{n^k}{k!}, \end{align*}where the last equality holds by computation (or since the bounds are sharp at equality, details omitted). \(\blacksquare\)