All Questions
43 questions
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 13
17
votes
1
answer
1k
views
Can the Pythagorean Graph be finitely colored?
Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, ...
- 5,103
4
votes
0
answers
113
views
What properties do graphs avoiding large regular subgraphs have?
Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
- 557
4
votes
1
answer
190
views
Independent sets in graphs with girth $\ge g$
A well known off-diagonal Ramsey result says that every $C_3$-free graph $G$ on $N$ vertices has an independent set of size $\Omega(\sqrt{N\log N})$.
It is a conjecture of Erdos that every $C_4$-free ...
- 3,499
8
votes
1
answer
392
views
What is this Ramsey problem?
Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
- 3,499
8
votes
0
answers
232
views
On the structure of maximal Ramsey colorings
For positive integers $a_1,\dots,a_n$, recall that the multicolor Ramsey number $R(a_1,\dots,a_n)$ is the smallest integer $N$ such that if the edges of the complete graph $K_N$ are colored with the $...
- 32.5k
3
votes
2
answers
275
views
Ramsey-Turán density function is well defined
Define
$$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$
and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as
$$f_l(\alpha)=\lim_{n\to \infty}...
- 227
7
votes
2
answers
595
views
A 2-page paper on a lower bound of Ramsey number
I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the ...
- 71
0
votes
0
answers
138
views
Original Paper for "Bipartite Ramsey Theory" by Hattingh, Johannes H, 1998
I'm trying to find the original paper "Bipartite Ramsey Theory" by Hattingh, Johannes H., Util. Math. 53 (1998), 217–230. However, I couldn't find it online except Mathsci.
Does anyone ...
- 139
2
votes
1
answer
396
views
Best known upper bound for the Ramsey function $R(k,x)$
The Ramsey function $R(k,x)$ is defined as the minimal integer $n$ such that any graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $x$. Miklós Ajtai, János ...
- 622
6
votes
1
answer
194
views
Graphs with linear Ramsey number for two colors, but super-linear Ramsey number for three colors?
Given a graph $H$, let $R_k(H)$ be the smallest integer $N$ such that in every $k$-coloring of the edges $K_N$ there is a monochromatic copy of $H$ (in other words, $R_k(H)$ is the ordinary $k$-color ...
- 1,701
4
votes
1
answer
230
views
Independence number of $C_4$-free graphs
It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$.
This bound cannot be improved over $\Theta(n^{\...
- 9,501
48
votes
8
answers
4k
views
Ron L. Graham’s lesser known significant contributions
Ron L. Graham is sadly no longer with us.
He was very prolific and his work spanned many areas of mathematics including graph theory, computational geometry, Ramsey theory, and quasi-randomness. His ...
6
votes
1
answer
403
views
Ramsey-Kuratowski numbers
A simple graph is an ordered pair of sets $\,\Gamma:=(V\,E)\,$ such that
$\,E\subseteq\binom V2.\ $ Kuratowski graph of the first kind is
$\,K_n:=\left(V\,\,\binom V2\right),\,$ where $\,n:=|V|.\,$ ...
- 4,786
2
votes
0
answers
603
views
Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory?
As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that $R(5,5)\leq 47$.
According to the Dynamic Survey of Ramsey Numbers at ...
- 29
5
votes
0
answers
77
views
Consequences of Ramsey-numbers of hypergraphs
We know that the (2-color) Ramsey-numbers for $3$-uniform hypergraphs are between roughly $2^{n^2}$ and $2^{2^n}$, and the situation is similar to $k$-uniform hypergraphs for every $k\ge 3$. (A recent ...
- 18.8k
6
votes
1
answer
284
views
Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?
Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...
- 1,203
3
votes
2
answers
340
views
A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?
Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a ...
- 1,701
15
votes
1
answer
2k
views
Ramsey Number R(3,3,4)
How much is known about the Ramsey number R(3,3,4)? There is a trivial upper bound of 34, but are any tighter bounds known?
- 2,811
6
votes
1
answer
119
views
Containment of minimal 2-Ramsey-graphs in minimal 3-Ramsey-graphs
Let $G$ be a minimal $2$-colour Ramsey-graph for $H$.
Must there exist a minimal $3$-colour Ramsey-graph $F$ for $H$ with $G\subset F$?
I am wondering if anything is known about this, particularly ...
- 277
4
votes
1
answer
213
views
Finding a monochromatic cycle in clique
1) what is the minimum $n$ such that in every $2$ - coloring of $K_n$ there exist a monochromatic copy of $C_m$ ?
2) moreover, what is the minimum $n$ such that in every $r$ - coloring of $K_n$ there ...
- 41
9
votes
1
answer
1k
views
What is the upper bound of $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$ times}$?
Just some context: $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$ times}\leq n$, means that any colouring of a complete graph, $k_n$, on $n$ vertices or more with $k$ colours must contain a monochromatic ...
- 91
4
votes
0
answers
460
views
Bounding Ramsey numbers with quadratic or higher residues
For parameters $m,k$, we call a graph on $n$ vertices Ramsey if it contains no complete subgraph on $m$ vertices and its complement contains no complete subgraph on $k$ vertices (or vice versa). The ...
- 41
5
votes
1
answer
310
views
A variant of Ramsey numbers
The well known Ramsey number $R(k)$ is the least integer $n$ so that every 2-edge coloring of $K_n$ contains a monochromatic $K_k.$
Another interpretation of the above definition is that every graph ...
- 3,463
10
votes
3
answers
490
views
How many colors do we need to avoid bichromatic triangles?
Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors.
I wonder if the following type of question has ...
- 18.8k
11
votes
0
answers
243
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 ...
- 18.8k
4
votes
1
answer
164
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 ...
- 141
19
votes
0
answers
625
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 ...
- 17.6k
0
votes
0
answers
96
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 $\beta\...
- 13.9k
7
votes
2
answers
362
views
Reference request: monochromatic paths in edge-colored complete graphs
Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.
...
- 71
36
votes
0
answers
2k
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 = (\alpha,...
- 17k
15
votes
1
answer
2k
views
Could there be an exact formula for the Ramsey numbers?
Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$.
Is it possible that there ...
- 7,013
3
votes
1
answer
679
views
Big binary tree as an induced subgraph
I believe this is true:
Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an
induced subgraph which is a subdivision of a large binary tree or the line ...
- 625
2
votes
1
answer
222
views
Coloring of subgraphs of G^n
Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , \overline{r}=(r_1,...,...
- 85
6
votes
2
answers
317
views
Is there a graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free
Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nešetřil and Rödl proved that for every graph $G$, there exists a graph $F$ such that ...
- 61
5
votes
1
answer
749
views
Small Ramsey numbers and Brooks' Theorem
I'm studying about Graph Ramsey Theory now. Starting this study, I'm reading Chvatal and Harary's series of papers. In the second paper (V.Chvatal, F.Harary, Generalized ramsey theory for graphs,Ⅲ. ...
- 363
2
votes
1
answer
276
views
A Ramsey-like lower bound?
Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there is ...
- 2,350
4
votes
1
answer
225
views
Large bicliques in r-partite graphs containing no independent sets having one vertex from each class
Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a ...
- 495
1
vote
1
answer
571
views
Combinatorial optimization and graph coloring
I am considering the following problem:
(i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily.
(ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow \...
user14875
2
votes
0
answers
303
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 ...
- 21
10
votes
3
answers
1k
views
Asymptotics for Ramsey Theory
Ramsey Theory says that every sufficently large (but finite) complete graph having $d-$coloured edges contains a monochromatic complete subgraph with $k$ vertices.
One could ask for asymptotics: Let $...
- 17.9k
13
votes
3
answers
911
views
Differences of near diagonal Ramsey numbers.
I am a graduate student trying to get involved in Ramsey theory. My question comes from:
Erdős on graphs: his legacy of unsolved problems
By Fan R. K. Chung, Paul Erdős, Ronald L. Graham
p.14 of ...
- 124
15
votes
6
answers
2k
views
Can one make Erdős's Ramsey lower bound explicit?
Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...
- 2,967