Graph with set of vertices $V$=${n\choose k}$ and set of edges $E$=$\{uv:u\cap v=\emptyset\}$

Question

Let $G$ be a graph with set of vertices $V$=${n\choose k},1\leq k<\frac{n}{2}$, and set of edges $E$=$\{uv:u\cap v=\emptyset\}$. Find the number of edges, the degree of each vertex, and prove that for $k>n/3$ the graph has no triangles.

I have several problems with the notation of the problem.

The number of vertices is $n\choose k$ or are we making 'groups' of vertices?

In the set of edges, what does the intersection of two vertices mean? How can $u\cap v\neq\emptyset\ $?

Could you give me some hints to understand the notation of the exercise in an intuitive way? Thanks you in advance!

Answer 1

The notation ${n \choose k}$ is usually used for the number of $k$-subsets from a set of size $n$, but is also sometimes used for the actual collection of $k$-subsets of $\{1,2,\dots,n\}$.

In the context you give, each set of size $k$ is a vertex of the graph. Thus we can talk about the intersection of two vertices (since each vertex is in fact a set).

Answer 2

Probably, it is intended to have $ V = \{ X \subseteq \{1, ..., n \}~~|~~ |X| = k \}$.

Then the statement about triangles makes sense, because you cannot find three disjoint subsets of $ \{ 1, ..., n \}$ with cardinality $> n/3$ .

Answer 3

$V$ should be $[n]^{(k)}$ instead of $\binom{n}{k}$. There is an edge between two subsets $u,v$ if and only if they are disjoint. Then there are no triangles when $k$ is large because you can't find three large mutually disjoint subset.

Answer 4

There is one vertex corresponding to each $k$ element subset of an $n$ element set. There is an edge between the vertices if the corresponding sets are disjoint. To find the degree of each vertex note that a $k$ element subset is disjoint with all the $k$ element subsets formed from the $n-k$ element set. Then you can find the number of edges.