MATHNOTES

This is a collection of writeups of theorems and other things, in math, I find interesting and felt inspired to type in my notes for. NONE of these results are mine.

1. Ramsey Theory
   1. Ramsey's theorem for graphs ramsey.PDF.

   2. Three proofs of the Hypergraph Ramsey Theorem (in progress) higherramsey.PDF.

   3. An Application of Ramsey's Theorem to Proving Programs Terminate (An exposition, a rough draft) RAMSEYPL.PDF.

   4. An Exposition of Roth's Theorem which states that `big' sets of integers must contain arithmetic progressions of size 3. Formally          $(\forall \lambda>0)(\exists n_0\in N)(\forall n\ge n_0)(\forall A\subseteq [n])[\vert A\vert\ge \lambda n \rightarrow \hbox{$A$ has a 3-AP}].$ We present a combinatorial proof that is essentially due to Szemeredi. SZ.PDF.

   5. (This is not a repeat of the last item.) An Exposition of Roth's Theorem which states that `big' sets of integers must contain arithmetic progressions of size 3. Formally          $(\forall \lambda>0)(\exists n_0\in N)(\forall n\ge n_0)(\forall A\subseteq [n])[\vert A\vert\ge \lambda n \rightarrow \hbox{$A$ has a 3-AP}].$ We present Roth's proof which uses continous math. ROTH.PDF.

   6. An Application of Ramsey Theory to Communication Complexity PUDLAK.PDF. This is a writeup of part of Pudlak's paper An application of Hindman's Theorem to a problem on Communication Complexity

   7. Van Der Waerden's Theorem- the k=3 Case. For all c there exists W(c)} such that, if you were to c-color {1,...,W(c), then there would exist a sequence of three numbers, in arithmetic progression, that are the same color! We prove this in detail in VDW3.PDF. More generally still, for all c and for all k there exists W(c,k) such that, if you were to c-color {1,...,W(c,k)}, then there would exist a sequence of k numbers, in arithmetic progression, that are the same color!

   8. Equations and Infinite Colorings An Exposition by Stephen Fenner and William Gasarch Consider the following statement which we denote $S$: For every $\omega$-coloring of $R$ there exists $e_1,e_2,e_3,e_4$ that are all the same color such that $e_1+e_2=e_3+e_4$. Is $S$ true or false? This exposition shows that $S$ is true iff $CH$ is false. Hence $S$ is true iff $CH$ is false. Hence $S$ is ind of ZFC. RADOZFC.PDF.

   9. Bounds on the Large Ramsey Numbers An Expostion by Bill Gasarch We show that $L_2(k) \le 2^{k^{2k}}$ LARGERAMSEYTOOLONG.PDF. A better bound is here: LARGERAMSEY.PDF

   10. Eucliean Ramsey Theory ERAMSEY.PDF

   11. Ergodic proof of VDW's theorem ERGODIC.PDF Also good to have this cheat sheet while reading it: HANDOUT.PDF

   12. The Infinite Ramsey Theorem RAMSEYI.PDF

   13. Ramsey's original application of Ramsey's theorem RAMSEYORIG.PDF

   14. Ramsey Theory for Open Sets What if we color all infinite subsets of $N$¿:wq OPENRAMSEY.PDF

2. Logic
   1. It is well known that the Kolm function is not computable. The usual proof does not reduce to HALT. Hence it is plausible that the Kolm function is of intermediary complexity. Its not. Oh well. In this proof we give the (well known to some) proof that Kolm is equivalent to HALT. EASYKOLM.PDF.

   2. An Exposition of the Main Theorem in Enumerations of the Kolmogorov Function Authors of paper: Beigel, Buhrman, Fejer, Fortnow Grabowski, Longpre, Muchnik, Stephan, Torenvliet. Let $C(x)$ be the shortest description of $x$. It is known that $C$ is undecidable (the proof of this is also included). But what if we just want to, given $x$, enumerate $\le 17$ possibilities, one of which is $C(x)$. This manuscript shows that this cannot be done. KOLM.PDF.

   3. Duplicator Spoiler Games EF.PDF

   4. A statement in Second order True in ($R,+)$ false in $(Q,+)$. SECONDORDER.PDF

   5. Showing that a Propositional Logic is Incomplete. PROP.PDF

3. Complexity Theory
   1. Primality in P For the original paper see PRIMES. For a write up that is suitable for undergrads (but leaves out some of the proofs) see PRIMESHANDOUT.PDF. (NOTE- This is more of an algorithms result.)

   2. Hardness vs Randomness. Under certain Hardness assumptions you can derandomize a computation. This is a writeup of the first result, due to Nisan-Wigderson, in that area. HARDRAND.PDF. Cheat sheet: SHORTNW.PDF.

   3. If L is any set then SUBSEQ(L) is Regular SUBSEQ.PDF

4. Non-Ramsey Combinatorics
   1. Sum-Product Theorems An Expostion by Bill Gasarch We present proofs of the following two theorems:
      1. If $A$ is a set of $n$ reals then either $\vert A+A\vert$ or $\vert A\cdot A\vert$ is $\Omega(n^{5/4})$.
      2. If $A$ is a set of $n$ reals then either $\vert A+A\vert$ or $\vert A\cdot A\vert$ is $\Omega(n^{14/11}/(\log n)^{3/11})$.
      SUMPRODUCT.PDF.

   2. Fractional Graph Theory We just define the fractional chromatic number of a graph. FRACTIONAL.PDF.

   3. Monotone Sequence Game MONOGAME.PDF.

   4. TicTacToe Plus The Maker-breaker version of k-in-a-row on an nxn board. TTTSURPLUS.PDF.

5. The Weak Prime Number Theorem WEAKPNT.PDF.

6. Polynomials with Minimal Deviance- Chebyshev Polynomials CHEBY.PDF.