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$.

learn more… | top users | synonyms

28
votes
0answers
685 views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
16
votes
0answers
262 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 ...
6
votes
0answers
163 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 ...
6
votes
0answers
85 views

Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity. See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$. Is there an ...
5
votes
0answers
137 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$, ...
5
votes
0answers
85 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 ...
5
votes
0answers
198 views

Van der Waerden like theorem

I am trying to develop bounds for the function B(k) where B(k) is defined as the least such positive integer so that whenever the set $\{1,2,\cdots B(k)\}$ is partitioned into two parts at least one ...
4
votes
0answers
152 views

Weak Arithmetic Progressions

I am studying a special type of a sequence on the naturals which I am calling a weak arithmetic progression. Formally I call a k-sequence $x_1< x_2 \cdots< x_k$ a weak arithmetic progression ...
3
votes
0answers
219 views

Constructive lower bounds for multicolor Ramsey numbers

The $k$-color Ramsey number of the complete graph $K_n$, denoted with $R_k(n)$, is defined to be the smallest integer $t$, such that in any $k$-coloring of the edges of $K_t$, there is a complete ...
3
votes
0answers
104 views

Bound on how many 2-colored graphs have maxredclique $i$, maxblueclique $j$

Fix $i,j$. I want a bound $F(i,j)$ on the following: $\sum_{n=1}^\infty$ (the number of 2-colorings of the edges of $K_n$ such that the MAX RED clique is size exactly ...
2
votes
0answers
66 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$ ...
2
votes
0answers
267 views

What is the complexity of determining Ramsey Number?

In the notation of Garey and Johnson [1], two problems related to Ramsey Problem were defined: $\textbf{ARROWING}$ Instance: (Finite) graphs $F$, $G$ and $H$. Question: Does $F\rightarrow (G, H)$? ...
2
votes
0answers
273 views

Slightly improving bounds on two-color Ramsey numbers by globally pruning edges and counting connected vertices in instances of two-colored complete graphs

The two-color Ramsey number, $R(m, n)$, is the minimum number of vertices, $||V||$, in a complete graph necessary for there to exist a clique of order $m$ or an independent set of order $n$. In terms ...
1
vote
0answers
51 views

Genus tradeoffs in bipartite graph

Given $G$ as bipartite graph of genus $g(G)$ with number of vertices of each color being $N$ with $A$ as $N\times N$ biadjacency matrix. Denote $\bar{G}$ to bipartite graph of genus $g(\bar{G})$ of ...
1
vote
0answers
105 views

Mixed Tsirelson Norm

A couple of days ago I posted this question on Mathematics Stack Exchange. Surprisingly, so far, I haven't received any answers or comments about it (besides my own possible answer). Maybe I can get ...
1
vote
0answers
237 views

Any 2-coloring of the scope of equilateral triangle must create a monochromatic rectangular triangle ?

Hello All, I'm trying to prove something that we know that is correct but can't find how to do it or any example to show how to solve it. Any 2-coloring of the scope of equilateral triangle must ...
0
votes
0answers
81 views

A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...