
\documentclass[letterpaper, reqno,11pt]{article}
\usepackage[margin=1.0in]{geometry}
\usepackage{color,latexsym,amsmath,amssymb,graphicx}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\begin{document}
\pagenumbering{arabic}
\title{Math 341 Homework 6}
\date{}
\newtheorem{thm}{Theorem}
\maketitle
%
\vspace{-16 mm}
\begin{itemize}
\item This problem set will not be graded; it is for practice only.
%
\end{itemize}


\noindent {\bf 1. a.}
Give an example of a family of sets $\mathcal{F}=\{A_1,A_2,A_3,A_4\}$  that satisfies Hall's criterion, for which there exists a unique SDR.

\medskip

\noindent {\bf b.} Give an example of a family of sets $\mathcal{F}=\{A_1,A_2,A_3,A_4,A_5\}$  that satisfies Hall's criterion, for which there exists more than one SDR.

\medskip


\noindent{\bf 2.} Let $A_1,\ldots,A_n$ be sets, with $n\geq 3$. Suppose that for every set of indices $I\subset[n]$, we have
$$
|A(I)|\geq|I|+2.
$$

Let $x_1\in A_1$ and $x_2\in A_2$ with $x_1\neq x_2$. Prove that there exists $x_3,\ldots,x_n$ so that $(x_1,x_2,x_3,\ldots,x_n)$ is a SDR for $A_1,\ldots,A_n$. 

\medskip


\noindent{\bf 3.} Let $n = 7 = 2^2 + 2 + 1$. Write down 7 sets $A_1,\ldots,A_n$ so that $\mathcal{F} = \{A_1,\ldots,A_7\}$ is a family of subsets of $[7]$; each set $A_i$ has cardinality $3$; each number $x\in [7]$ is contained in 3 sets, and each pair of sets intersect in exactly one element.

\medskip


\noindent{\bf 4.} Define $\mathbb{Z}_2 = \{0,1\}$; if $a,b\in \mathbb{Z}_2$, we define $a+b=0$ if $a=0,b=0$ or $a=1,b=1$. We define $a+b = 1$ if $a=0,b=1$ or $a=1,b=0$ (this is called addition mod 2, or XOR). If $a,b\in\mathbb{Z}_2$, define $ab = 0$ if $a=0$ or $b=0$ (or both), and define $ab=1$ if $a=1,b=1$. With these definitions, $\mathbb{Z}_2$ is called a \emph{ring}. 

Let $\mathcal{P}=\mathbb{Z}_2^3\backslash\{(0,0,0)\}$, i.e. 
$$
\mathcal{P} = \{(0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)\}.
$$

For each $(a,b,c)\in\mathbb{Z}_2\backslash\{(0,0,0)\}$, define
$$
L_{(a,b,c)}=\{(x,y,z)\in \mathcal{P}\colon ax + by + cz = 0\},
$$
where addition and multiplication is performed according to the rules described above. For example, if $(a,b,c) = (1,0,1)$, then
$$
L_{(1,0,1)} = \{(x,y,z)\in\mathcal{P}\colon x+z = 0\}=\{(1,0,1),\ (1,1,1),\ (0,1,0)\}.
$$

Let $\mathcal{F}$ be the family of 7 sets
$$
\mathcal{F} = \{ L_{(a,b,c)}\colon (a,b,c)\in\mathbb{Z}_2\backslash\{0,0,0\} \}.
$$

Write down the 7 sets in $\mathcal{F}$ (we wrote down $L_{(1,0,1)}$ above; you need to write down the rest). 

\medskip
Remark: Observe that each pair of sets intersect in exactly one element; each set contains 3 elements, and each element of $\mathcal{P}$ is contained in exactly 3 of the sets from $\mathcal{F}$.


\medskip

\noindent{\bf 5.} Let $\mathcal{F}$ be a family of subsets of $[n]$. Suppose that each set in $\mathcal{F}$ has cardinality $k$, and that for every collection of $k+1$ sets $A_1,\ldots,A_{k+1}\in \mathcal{F}$, we have that their intersection $A_1\cap A_2\cap\ldots\cap A_{k+1}$ is non-empty. Prove that the intersection of all the sets in $\mathcal{F}$ is non-empty, i.e. all of the sets in $\mathcal{F}$ contain a common element.  

\medskip


\noindent{\bf 6.}
An intersecting family $\mathcal{F}$ of subsets of $[n]$ is called \emph{maximal} if every larger family $\mathcal{F}^\prime\supsetneq\mathcal{F}$ is \emph{not} intersecting. I.e. it is impossible to add an additional set to $\mathcal{F}$ so that the resulting family is still intersecting.

Prove that every maximal intersecting family of subsets of $[n]$ has cardinality $2^{n-1}$.

\end{document}