
\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{mathrsfs}
\addtolength{\topmargin}{-.5in} \addtolength{\textheight}{1in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\evensidemargin}{-.6in} \addtolength{\textwidth}{1.2in}
\usepackage{latexsym,amsmath,amssymb,amsfonts,epsfig,graphicx,cite,psfrag}
\usepackage{eepic,color,colordvi,amscd}


\def\qed{\hfill \rule{4pt}{7pt}}

\def\pf{\noindent {\it Proof. }}




\pagestyle{plain}


\begin{document}
\begin{center}
    \large{Combinatorics, 2020 Fall, USTC} \\
    {Homework 7}
\end{center}



\begin{itemize}
\item The due is on Tuesday, Nov. 17, at beginning of the class.
\end{itemize}

\noindent{\bf 1.}
Prove that for any intersecting family $\mathcal{F}\subset 2^{[n]}$, there exists an intersecting family $\mathcal{F}'\subset 2^{[n]}$ satisfying that $|\mathcal{F}'|=2^{n-1}$ and $\mathcal{F}\subset \mathcal{F}'$.

\bigskip

\noindent{\bf 2.} Let $G$ be an $n$-vertex $d$-regular graph and let $\lambda_1\geq \lambda_2\geq ...\geq \lambda_n$ be the eigenvalues of $G$.
Prove that $\lambda_1=d$.


\bigskip

\noindent{\bf 3.} Given the same conditions as in the previous problem, prove that if $G$ is bipartite, then $\lambda_n=-d$.

\bigskip

\noindent{\bf 4.} Find the maximum number of line segments that a Hasse diagram of a poset $(X,\prec)$ with $|X|=n$ can have.
Then define a poset which achieves this maximum number and draw its Hasse diagram.


\bigskip


\noindent{\bf 5.} For two natural numbers $a,b$, the symbol $a|b$ means that ``$a$ divides $b$". In other words, there exists a natural number $c$ such that $b=ac$.
First verify that the relation ``$|$" is a partial ordering on the set $\mathbf{N}$ of natural numbers.
Then prove that every finite poset can be embedded into $(\mathbf{N},|)$.






\end{document}
