# Tagged Questions

Branch of combinatorics with the philosophy that 'total disorder is impossible'. For example, Ramsey's theorem asserts that for each $n$, every sufficiently large graph either contains a clique of size $n$ or a stable set of size $n$.

123 views

### Lower bound construction for Multidimensional Szemerédi's Theorem

The Multidimensional version of Szemerédi's theorem given by Theorem 10.2 in Tim Gower's paper from 2007 has the following statement. Let $\delta>0$ and $k\in\mathbb{N}$. Then if $N$ is ...
4k views

### Why is this new result such a big deal?

This popular article reports a recent result in reverse mathematics, showing that a certain theorem in Ramsey theory is provable from RCA$_0$, the base theory in SOSOA. Then there are a bunch of ...
113 views

### An extremal combinatorics problem involving column summation

Given $n\in\Bbb N$, $\alpha>0$, $\beta\in\big[\frac12,1\big]$ denote $\mathcal R_{n,\alpha,\beta}$ as collection of all $2^n\times 2^{n^\alpha}$ $0/1$ matrices with every row summing to strictly ...
133 views

### question about literature in the field of Ramsey's theory [closed]

i am searching for an on- line paper or a book, or maybe just a paper or a book which consists a proof of finite Ramsey's theorem for sets (not for graphs). i need a combinatorial proof which is not ...
192 views

### The Hales-Jewett Theorem for an infinite alphabet

Recall the Hales-Jewett Theorem: HJT: Given a finite alphabet $A$ and some $r \in \mathbb{N}$, there is some $H \in \mathbb{N}$ such that whenever $A^H$, the set of all length-$H$ words from $A$, ...
99 views

### Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
116 views

### Partition regular systems: do they have solution in (very dense) set of integers?

A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ classes,...
324 views

### Convergence rate of Fagin's 0-1 law for first-order properties of random graphs

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...
76 views

### Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

You are given a multigraph $G$ with $n$ vertices as follows: $V := (v_1, v_2, \dots ,v_n)$ $C := \{c_1, c_2, \dots\}$, be an infinite set of colors. $f: V \rightarrow \mathbb{P}_{\le m}(C)$, a ...
287 views

### Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture. But for bigger Ramsey ...
78 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
83 views

165 views

### A generalization of SOCA

Roughly speaking, SOCA (Semi Open Coloring Axiom) says that for an open coloring of the unordered pairs over an uncountable separable metric space you can always find an uncountable homogeneous subset ...
51 views

319 views

### Geometric van der waerden theorem

Van der Waerden theorem states that sufficiently long initial segment of the natural numbers when divided into $r$ parts contains an arithmetic progression of length $k$. The length of the initial ...
127 views

### Multipartite Ramsey theorem

Given $c<\infty$ colors, positive integers $k_1,\dots,k_n$ and positive integers $N_1,\dots,N_n$. Then there exist positive integers $M_1,\dots,M_n$ so that for disjoint finite sets $A_1,\dots,A_n$ ...
196 views

519 views

### Combining van der Waerden's theorem with Ramsey's theorem

Consider positive integers $c$, $k$, and $s$. Does there exist some $N = N(c,k,s)$ such that the following holds? Take any $c$-coloring of the $k$-tuples of integers in $[1,N]$. Then there is an ...
203 views

### What is a Ramsey Graph? [closed]

Can anyone explain me what is a Ramsey Graph with a simple example? What are its properties?
250 views

### Van der Waerden's Theorem Over $\mathbb{Z}_p$

Define a length $k$ arithmetic progression in $\mathbb{Z}_p$ to be a set of the form $\{ax+b : x \in [k]\}$ with $a \in \mathbb{Z}_p^*$ and $b \in \mathbb{Z}_p$. Let $HJ(k, c)$ be the Hales-Jewett ...
1k views

### A General Framework for Ramsey Theory ?

There are few results in modern mathematics that I find so deep and full of philosophical implications as Ramsey's theorem. I am aware (at some basic level) that it has generated a plethora of ...