\section{Background and results}
The following conjecture appears in a recent paper of Friedgut,
Kalai and Kindler.
\begin{conj}[\cite{FKK}, Conjecture 3.1]
\label{c11}
For every $\alpha \in (0,1/2)$ there exists $k$ and $\tau>0$ 
such that if $G$ is a graph on $n$ vertices with maximum
independent set of size $\alpha n$, then there exist pairwise
disjoint subsets of vertices $A_1,A_2, \ldots ,A_r$ in $G$
such that 
\begin{enumerate}
\item
$|A_i|=k $ for all $i$.
\item
$|\cup_{i=1}^r A_i| \geq \tau n$
\item
Every maximum independent set in $G$ intersects every set $A_i$.
\end{enumerate}
\end{conj}
Here we show that this is false for every fixed $\alpha \in
(0,1/2)$ even if the requirement (2) is omitted, but that the
assertion does hold for any $\alpha >1/2$. We also discuss several
related problems.

For a graph $G=(V,E)$ let $h(G)$ denote the minimum cardinality of
a set of vertices that intersects every maximum independent set of
$G$. Bollob\'as, Erd\H{o}s and Tuza (see \cite{Er}, page 224, or
\cite{CG}, page 52) conjectured that for any positive $\alpha$,
if the size $\alpha(G)$ of a
maximum independent set in an $n$ vertex graph $G$ 
is at least $\alpha n$, then $h(G)=o(n)$.
(They formulated the conjectures for cliques and not for
independent sets; replacing $G$ by its complement leads to the
formulation above.)
\begin{theo}
\label{t12}
For every positive integer $k$ there is a graph $G=G_k$ with
$n=2k(k-1)$ vertices, independence number $\alpha(G)=k^2 (> n/4)$,
and $h(G)=k+1 (> \sqrt {n/2}).$
\end{theo}
\begin{theo}
\label{t13}
For any positive integers $m$ and $t$, where $m$ is even and $4t^2
\leq m$,
there is a graph $G=G_{m,t}$ on $n=2^m$ vertices with independence number 
$\alpha(G)=\sum_{i=0}^{m/2-t} { m \choose i}$ and
$h(G)=\Theta(t^2)$.
\end{theo}
The above two results provide counterexamples to
Conjecture \ref{c11}. On the other hand we observe that an old
result of Hajnal implies that the
assertion of the conjecture (with $k=1$ and $\tau=2\alpha-1$) 
does hold for any $\alpha >1/2$. Using this result we prove that 
if the independence number of an $n$-vertex graph $G$ is
$\alpha n$ where $\alpha=(1/4+{\varepsilon})n$, 
then the average value of the independence number
of an induced subgraph of $G$ on a uniform random subset of the vertices
is at most $(\alpha-\Omega({\varepsilon}^2))n$. This is motivated by
another conjecture raised in \cite{FKK}, proving it for the
simplest nontrivial range of the parameter $\alpha$.

\section{Proofs}

\noindent
{\bf Proof of Theorem \ref{t12}:}\, 
The graph $G=G_k$ is the shift graph described as follows.
Put $K=\{1,2,.., 2k\}$. The  set of 
vertices of $G_k$ is the set of all
ordered pairs $(i,j)$ with $i \neq j$ and $i,j \in K$. Thus the 
number of vertices is 
$n=2k(2k-1)$. Two vertices $(a,b)$ and $(c,d)$ are adjacent
if $b=c$ or $d=a$.
Note that the vertices can be viewed as all
directed
edges of the complete directed graph on $K$, where 
two are adjacent iff they form
a directed path of length $2$. It is easy to check 
that the maximum independent sets of this graph are of size
$k^2$. Indeed, for every partition of $K$ into two disjoint 
parts $S$ and $T$
of equal cardinality, the set of all
pairs $(s,t)$ with $s \in S, t \in T$ is a maximum independent
set, and these are all the maximum independent sets.
Any set $H$ of at most $k$ vertices of $G$ can be viewed as
$k$ directed edges of the complete graph on $K$. Let $S$
be a set of $k$ points in $K$ that does not contain the 
head of any of these $k$ directed edges, and put $T=K-S$.
Then the maximum independent set consisting of all
pairs $(s,t)$ with $s \in S, t \in T$ does not intersect $H$.
Therefore $h(G) \geq k+1$. This is tight as shown by 
a set of pairs forming a directed cycle of length $k+1$ in the
complete directed graph on $K$. \hfill $\Box$
\vspace{0.2cm}

\noindent
{\bf Proof of Theorem \ref{t13}:}\, 
Let $G=G_{m,t}$ be the graph whose vertices are all binary vectors
of length $m$, where two are adjacent iff the Hamming distance
between them exceeds $m-2t$. Note that this is the Cayley graph
of $Z_2^m$ with respect to the set of all vectors of Hamming weight
at least $m-2t+1$. This graph contains as an induced subgraph
the Kneser graph $K(m,m/2 +1 -t)$.
By an old result of Kleitman \cite{Kl},
the independence number of this graph is
exactly $\sum_{i=0}^{m/2-t} {m \choose i}$.
The maximum independent sets are the $2^m$ Hamming
balls of radius $m-t$ centered at the vertices of $G$. Any set of
vertices that hits all these independent sets forms a covering code
of radius $m/2-t$ in $Z_2^m$. By using known results about covering
codes  in this range of the parameters 
it is not
difficult to prove that the minimum possible size of such a set is
$\Omega(t^2)$. Indeed, viewing the vectors of the covering code
as vectors with $\{-1,1\}$ coordinates, if their number is $T$ then 
by a known result in Discrepancy Theory (see, e.g., \cite{AS}, 
Corollary 13.3.4), there is a $\{-1,1\}$ vector whose inner product 
with all members of the code is in absolute value at most
$12 \sqrt T$. If $12 \sqrt T < 2t$ this gives a vector 
whose Hamming distance from any codeword is larger than $m/2-t$,
contradicting the assumption. This shows that the size of the code
is at least $\Omega(t^2)$. 
This is tight up to the hidden constant in the
$\Omega$-notation as can be shown by a random construction of
vectors of length $\Theta(t^2)$, extending each such vector in two
complementary ways on the remaining coordinates, or by taking the
rows of a Hadamard matrix of order $\Theta(t^2)$ and their
inverses, extending them in the same way.
Note that the fact that the Kneser graph
$K(m,m/2+1 -t)$ is a subgraph of $G$ also
implies a lower bound of $2t$ for the size of the hitting set
(as the Hamming balls  of radius $m/2-t$ centered in the points of
the hitting set cover all points, providing a proper coloring of the
Kneser graph), but the bound obtained this way is weaker than the
tight $\Theta(t^2)$ bound. \hfill  $\Box$

\section{Remarks}

\begin{itemize}
\item
An old result of Hajnal \cite{Ha} (see also \cite{Ra}) asserts
that for every graph $G$ the cardinality of the intersection of all 
maximum independent sets plus the cardinality of the union of all
these sets is at least $2 \alpha(G)$.  If $\alpha(G) = \alpha n$
where $\alpha>1/2$ and $n$ is the number of vertices of $G$,
this implies that there is a set of at least $(2\alpha
-1)n$  vertices contained in all maximum independent sets. 
(The result in \cite{Ha} is formulated in terms of cliques, and not 
in terms of independent sets, but this is clearly equivalent as
shown 
by replacing the graph with its complement). 
This shows that the assertion of Conjecture
\ref{c11} holds for $\alpha>1/2$ (with $k=1$ and $\tau=2\alpha-1$).
\item
Using the result of Hajnal mentioned above we obtain some
(modest) progress on another conjecture raised in \cite{FKK}.
For a graph $G$ on $n$ vertices 
and independence number $\alpha(G)=\alpha n$,
let $\alpha'n=\alpha'(G)n$ 
denote the average value of the independence number of
the induced subgraph of $G$ on a uniform random set of
vertices. 
\begin{conj}[\cite{FKK}, Conjecture 2.9]
\label{c31}
For any $\alpha \in (0,1/2)$ there is an ${\varepsilon}={\varepsilon}(\alpha)>0$
so that for every graph $G$ with $n$ vertices and 
independence number $\alpha n$,
$\alpha'(G) \leq \alpha-{\varepsilon}(\alpha)$.
\end{conj}
The following result shows that the above is true for any
$\alpha > 1/4$. The case of positive $\alpha$ close to $0$ appears
to be significantly more difficult (and interesting).
\begin{theo}
\label{t32}
Let $G=(V,E)$ be a graph with $n$ vertices and independence
number $\alpha(G) = (1/4+{\varepsilon})n$, where ${\varepsilon}>0$ satisfies
${\varepsilon}<1/4$. Then 
$\alpha'(G) \leq 1/4+{\varepsilon}-{\varepsilon}^2/3$.
\end{theo}

The constant $1/3$ above can be easily improved and we make no attempt to
optimize it here.

\noindent
{\bf Proof:}\,  Without loss of generality we may assume that
$n$ is arbitrarily large, as we can replace $G$ by a union
of many vertex disjoint copies of itself and use linearity of
expectation. Assuming $n$ is large, almost every random subset of
vertices is of cardinality $(1/2+o(1))n$, hence it suffices to
show that for almost every set $W$ of $m=(1/2+o(1))n$ vertices,
the independence number of the induced subgraph of $G$ on $W$ is
smaller than $(1/4+{\varepsilon}-{\varepsilon}^2/2)n$. Construct the random set $W$
of size $m$ by  removing from $G$ vertices, one by one. Starting
with $V=V_0$, let $V_{i+1}$ be the set obtained from $V_i$ by 
removing a uniform random vertex of $V_i$. The set $W$ is thus
$V_{n-m}$. Let $G_i$ be the induced subgraph of $G$ on $V_i$.
Call a step $i$, $1 \leq i \leq
n-m$ of the random process above 
successful if either the independence number of 
$G_{i-1}$ is already smaller than $(1/4+{\varepsilon}-{\varepsilon}^2/2)n$
(note that in this case this will surely be the case in
the final graph $G_{n-m}$), or the independence number
of $G_{i}$ is strictly  smaller than that of $G_{i-1}$.
Put $i_0=(1/2-{\varepsilon})n$ and consider the graph 
$G_{i_0}$. For any
$i >i_0$, the number of vertices of $G_{i-1}$ is at most
$(1/2+{\varepsilon})n$. If its independence number is  smaller than
$(1/4+{\varepsilon}-{\varepsilon}^2/2)n$ then, by definition, step number $i$ is 
successful. Otherwise, by the result of Hajnal mentioned above,
the number of vertices of $G_{i-1}$ that lie in all the maximum
independent sets in it is at least $({\varepsilon}-{\varepsilon}^2)n$. Since ${\varepsilon} <1/4$
this is a fraction of at least  ${\varepsilon}$ of the vertices of
$G_{i-1}$. Therefore, in this case,
the probability that the next chosen vertex lies in all maximum
independent sets of $G_{i-1}$ is at least ${\varepsilon}$. 
We have thus shown that for every $i$ satisfying $i_0<i  \leq n-m$
the probability that
step number $i$ is successful is at least $\epsilon$. Therefore,
the probability that there are at least ${\varepsilon}^2 n/2$ successful
steps during the $n-m-i_0=({\varepsilon}-o(1))n$ steps starting with
$G_{i_0}$ until we reach $G_{n-m}$  is at least the probability
that a binomial random variable with parameters
$({\varepsilon}-o(1))n$ and ${\varepsilon}$ is at least ${\varepsilon}^2 n/2$. This
probability is $1-o(1)$ for any fixed positive ${\varepsilon}$ as 
$n$ tends to infinity. Since having that many successful steps 
ensures that the independence number of the induced subgraph
of $G$ on $W$ is at most $(1/4+{\varepsilon}-{\varepsilon}^2/2)n$, this completes
the proof.  \hfill $\Box$
\item
A conjecture I raised more than ten years ago motivated 
by some of the results in \cite{AHLSW}
is that the chromatic number of the graph $G_{m,t}$ described
in the proof of Theorem \ref{t13}, where $4t^2 \leq m$,
is $\Theta(t^2)$. This has been mentioned in several lectures,
see, for example, \cite{Al}. By the arguments described in the
proof of Theorem \ref{t13} this chromatic number is at least
$2t$ and at most $O(t^2)$.
\end{itemize}

\noindent
{\bf Acknowledgment}
I thank Ehud Friedgut for helpful discussions.
