\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}