Finding an exponential number of subsets of $[n]$ that differ in $O(n)$ indices. Suppose we want to find an exponential number of subsets of $\{1,....,n\}$ s.t. for each two subsets, denoted as $S,T$ we have: $|(S\setminus T)\cup(T\setminus S)|=\Omega(n)$. Since there are at most $2^n$ subsets this means that the set we are looking for is of cardinality $2^{\Omega(n)}$, any thoughts on how to construct it?
 A: Let $\alpha \in (0,1)$ and define $\Delta(S,T)$ as the symmetric difference of sets, which is your quantity. You want to find a large set family $\cal F$ all of whose members are subsets of $\{1,2,\ldots,n\}$ such that
$$
S\neq T \in {\cal F} \Rightarrow \Delta(S,T)\geq \alpha n.
$$
In the language of coding theory, where the support of a set $A$ can be associated with a binary vector $c_A=(\chi[k \in A]: 1\leq k\leq n),$ where $\chi(\cdot)$ is the indicator function of an event, you are looking for a code with positive rate and minimum distance.
So you want to find exponentially many binary codewords of length $n$, all of which differ pairwise in at least $\alpha n$ coordinates, which is the minimum distance of the code.
Such collections of codewords exist, by random coding arguments, explicitly constructing them is harder.
The Gilbert-Varshamov lower bound (in asymptotic form) states that for $n$ large enough there is a code $C$ of rate $R$ (where $R=\log_2(\#C)/n$ and minimum distance $\alpha n$ provided the inequality
$$
R\geq 1-H_2(\delta)
$$
where $H_2$ is Shannon entropy. The finite version is that there exists a code satisfying
$$
\#C\geq \frac{2^n}{\sum_{j=0}^{\lfloor \delta n\rfloor-1} \binom{n}{j}}
$$
where the sum below is the number of binary vectors within distance $\delta n$ of a given codeword, the volume of a so-called Hamming sphere of radius $d-1.$
As for constructions, explicit deterministic constructions are hard to come by.
