The tag has no wiki summary.

learn more… | top users | synonyms

25
votes
0answers
622 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 = ...
6
votes
0answers
157 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
81 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
193 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
151 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
211 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
50 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
187 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
253 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
47 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
101 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
235 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
65 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 ...