Due Tuesday, March 13 at noon.
Teaching blog
Andrés Caicedo
Recent Comments
Mathoverflow- Answer by Andrés E. Caicedo for Counterintuitive consequences of the Axiom of Determinacy?
- Answer by Andrés E. Caicedo for Perfect set property for projective hierarchy
- Answer by Andrés E. Caicedo for Is all ordinary mathematics contained in high school mathematics?
- Answer by Andrés E. Caicedo for Which types of Diophantine equations are solvable?
- Convergence of $\sum(n^3\sin^2n)^{-1}$
- Answer by Andrés E. Caicedo for Well known theorems that have not been proved
- Answer by Andrés E. Caicedo for Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper?
- Answer by Andrés E. Caicedo for The Erdős-Turán conjecture or the Erdős' conjecture?
- Relative densities
- On the division paradox
- Math.StackExchange
- Answer by Andrés E. Caicedo for Why König's lemma isn't "obvious"?
- Answer by Andrés E. Caicedo for Mapping Reflection Principle
- Answer by Andrés E. Caicedo for Proving $\kappa^{\lambda} = |\{X: X \subseteq \kappa, |X|=\lambda\}|$
- Answer by Andrés E. Caicedo for ZFC results first proved using $V=L$ or the diamond principle?
- Answer by Andrés E. Caicedo for Reference for combinatorial game theory.
- Answer by Andrés E. Caicedo for Inequality Regarding Subtraction of Transfinite Cardinals. Is this correct? $\aleph_0 - \aleph_0 \le \aleph_0$
- Answer by Andrés E. Caicedo for When can you subtract cardinals? Does $|A|+|C|=|B|+|C|>|C|$ imply $|A|=|B|$ in ZF?
- Answer by Andrés E. Caicedo for Which forcing axioms may be destroyed through forcings which preserve $2^{\aleph_0}=\aleph_2$?
- Answer by Andrés E. Caicedo for What is the cardinality of $A \times \mathbb N$ if $\left \lvert A \right \rvert \geq \aleph_0\ $?
- Answer by Andrés E. Caicedo for Any partition of an at most countable set has a set of representatives.
Teaching blog 
On page 3, Definition 1.6 and 1.9 seems to have the role of k and n switched–is this intentional or a mistake?
I can see it both ways, and I can probably think about the hint for Problem 1 more and figure out what these notation mean, but I am a bit confused right now, so I thought I would just ask here.
That would definitely make more sense, as I’m trying to work through the hint on 1 and getting essentially that (since k >= 2n + 1) “given a graph of size 2n+1, there is a monochromatic subgraph of size >= 3n+1.” I guess that works when n = 0 and k = 2n+1.
Wait, no, but switching them makes the homogeneity definition break… with the switching, this is what I get.
f : {1, …, w}^[k+n] –> {1, …, e + 2}
But |H| = 2n + 1.
Since H’s homogeneity refers to the size of the sets in the domain of f, we then have that “for all A, B in H^[k+n]”… but there are no subsets of H of size k + n (unless, again, n = 0 and k = 2n+1).
—-
I’m rather confused in general, actually, about the translation from the notation to words. Let’s try Ramsey’s theorem in words… (assume all graphs are connected)
“for all ???s k and subgraph sizes n, and all finite sets of colors C, there is a minimum graph size M such that for all graphs X of size >= M and all colorings f, some subgraph of H of size >= n will be colored the same way twice?”
That’s all wrong. Help anyone?
I think it might make more sense if we’re dealing with hypergraphs? Here’s what I have now…
“For all n and k >=1, and all finite sets of colors C, there is a M such that for all graphs X of size at least M and all colorings f that assign k edges in X to a color in C, there is a subgraph H of size at least n in X such that all k-sized subgraphs of H have the same coloring.”
The coloring doesn’t make much sense unless we can assign each edge multiple colorings…
Also, why can we take k >= 2n+1? I thought we had to prove this for ANY k and ANY n.
Regarding why we can take k >= 2n+1: I think if we proved that there is a set H in N^[k] of diagonal indiscernibles, then a subset of H also works.
Hi. Sorry for not having seen these before. Hmm… In the hint I want 2n+1 to be the size of the tuples the coloring is defined on and k+n (or w) to be the size of the homogeneous object. So: the superindex indicates the sizes of the tuples being colored, the number in parentheses indicates the size of the (min)-homogeneous object. The switch was an unfortunate typo on Definition 1.9.
Let’s see… Ramsey: Let’s say a k-hypergraph is a set A together with a relation on k-subsets of A (k-edges). So a (non-directed) graph (without loops) is just a 2-hypergraph. Is this the usual notation? The size of such a beast is the number of vertices, |A|. It is complete iff each k-edge is in the relation. Then Ramsey’s result becomes: “For all n and k >=1, and all finite sets of colors C, there is an M such that given any coloring f that assigns to each k-edge of the complete k-hypergraph of size M a color in C there is a complete (sub)-k-hypergraph H of size at least n such that all its k-edges have the same coloring.”
For k=2 and 2 colors this can be said in an easier way: For all a there is b such that any (non-directed, without loops) graph in at least b vertices either contains a complete subgraph of size a or an empty subgraph of size a. (Empty meaning there are no edges between the vertices).
“Also, why can we take k >= 2n+1? I thought we had to prove this for ANY k and ANY n.”
If we have a homogeneous (or min-homogeneous) set of size 20, then certainly we have one of size 4. So: If we prove that for all colorings of n-edges we obtain a (min)homogeneous object of size a+2n+1 then we have certainly obtained one of size at least a, so we may as well assume that a is at least 2n+1. Also using the same idea, given any number z we may as well assume that the least number in the homogeneous set is at least z, since it suffices to obtain a homogeneous set of size z+a to ensure we have a homogeneous set of size a whose least element is at least z.