\documentclass[12pt,ifthen]{article}
\usepackage{amsmath,amssymb}
%\usepackage{html}
%\usepackage{url}
\usepackage{hyperref}
\newcommand{\spec}{\rm spec}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}
\newcommand{\finv}{f^{-1}}
\newcommand{\COL}{\mathrm{COL}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\begin{document}

\centerline{\bf Homework 7, Morally Due Tue April 21, 2020, 3:30PM}

COURSE WEBSITE: \url{http://www.cs.umd.edu/~gasarch/858/S18.html}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!!!!}

\begin{enumerate}

\item
(0 points)
What is your name?  Write it clearly.


\item
(40 points) Find 
polynomials $X_0(n)$, $X_1(n)$, $X_2(n)$ and $X_3(n)$ so that 
(1) they are monotone increasing, and 
(2) THE FOUR STATEMENTS below are true.
The polynomials must be expressed so the coefficients are clear, something like:

$$\frac{87n^2}{13} + \frac{163n}{85} + \frac{17n}{35} - \frac{31}{14}$$

(This is not close to the answer and the answer need not be quadratic.)

You need to DERIVE the answer, not just write down polys which happens to work.

{\it Advice} Use Wolfram Alpha.

THE FOUR STATEMENTS:

\begin{itemize}
\item
Let $n\equiv 0 \pmod 4$. 
 For all 2-colorings of the edges of $K_n$ there exists $\ge X_0(n)$ monochromatic $K_3$'s.
\item
Let $n\equiv 1 \pmod 4$. 
 For all 2-colorings of the edges of $K_n$ there exists $\ge X_1(n)$ monochromatic $K_3$'s.
\item
Let $n\equiv 2 \pmod 4$. 
 For all 2-colorings of the edges of $K_n$ there exists $\ge X_2(n)$ monochromatic $K_3$'s.
\item
Let $n\equiv 3 \pmod 4$. 
 For all 2-colorings of the edges of $K_n$ there exists $\ge X_3(n)$ monochromatic $K_3$'s.
\end{itemize}


\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(30 points- 15 points each)

\begin{enumerate}
\item
Give sentence $\phi$ in the lang of  graphs with  $SPEC(\phi)=\{100\}$.

\item
Give sentence $\phi$ in the lang of graphs with $SPEC(\phi)=\{0,3,6,\ldots\}$.
\end{enumerate}


\item
(30 points) We are looking at the language of colored $\le 3$-ary hypegraphs.
Hence we have the following predicates:
\begin{itemize}
\item
$RED(x)$, $BLUE(x)$.
(so single vertices can be colored RED or BLUE or not at all).
\item
$RRED(x,y)$, $BBLUE(x,y)$, $GGREEN(x,y)$.
(so 2-ary edges colored RRED or BBLUE or GGREEN or not at all).
\item
$RRRED(x,y,z)$, $BBBLUE(x,y,z)$.
(so 3-ary edges colored RRRED or BBBLUE or not at all).
\end{itemize}

So a sample sentence is

$(\exists x_1,x_2,x_3,x_4)(\forall y)[RED(x_1)\wedge BLUE(x_2) \implies BBBLUE(x_1,x_2,y)]$

Show that the following is decidable:

Given a $E^*A^*$ sentence, return $\spec(\phi)$ (which will always be finite or cofinite).

You can assume the standard hypergraph Ramsey Theorem, but aside from that you must
prove it from scratch. Here is our Litmus test: Someone in this class who missed
my lecture on this should be able to read your proof and understand it.


\end{enumerate}

\end{document}