Search Results

We settle the Ramsey problem $\mathcal{R}(K_6-e,K_4)$, also known as $\mathcal{R}(J_6,K_4)$ and $\mathcal{R}(K_6^{-},K_4)$. Previously, the best bounds were $30\le \mathcal{R}(K_6-e,K_4)\le 32$. We prove that $\mathcal{R}(K_6-e,K_4)=30$. Our technique is based on the recent approach of Angeltveit and McKay and on older ...

A graph G is q-Ramsey for a q-tuple of graphs ( H 1 , … , H q ) if for every q-coloring of the edges of G there exists a monochromatic copy of H i in color i for some i ∈ [ q ]. Over the last few decades, researchers have investigated a number of ...

Let G, H be two non-empty graphs and k be a positive integer. The Gallai-Ramsey number ${\text{gr}}_k(G:H)$ is defined as the minimum positive integer N such that for all $n\ge N$, every k-edge-coloring of $K_n$ contains either a rainbow subgraph G or a monochromatic ...${}_{}$${}_{{}_{}}$

For any integer $h⩾2$, a set of integers $B={\{b_i\}}_{i\in I}$ is a $B_h$-set if all h-sums $b_{i_1}+\dots +b_{i_h}$ with $i_1<\dots <i_h$ are distinct. Answering a question of Alon and Erdős [2], for every $h⩾2$ we construct a set of integers X which is not a union of finitely many $B_h$-...$$${}_{}$$$$$${}_{}$${}_{}{}_{}$

We show that, for any prime p and integer $k\ge 2$, a simple $\text{GF}(p)$-representable matroid with sufficiently high rank has a rank-k flat which is either independent in M, or is a projective or affine geometry. As a corollary we obtain a Ramsey-type ...$$$\mathrm{}$$$

For a set of positive integers D, a k-term D-diffsequence is a sequence of positive integers a 1 < a 2 < … < a k such that a i − a i − 1 ∈ D for i = 2 , 3 , … , k. For k ∈ Z + and D ⊂ Z +, we define Δ ( D , k ), if it exists, to be the smallest ...

A famous result of D. Walkup is that an m × n rectangle may be tiled by T-tetrominos if and only if both m and n are multiples of 4. The “if” portion may be proved by tiling a 4 × 4 block, and then copying that block to fill the rectangle; but ...

Colour the edges of the complete graph with vertex set $\{1,2,\cdots ,n\}$ with an arbitrary number of colours. What is the smallest integer f(l, k) such that if $n>f(l,k)$ then there must exist a monotone monochromatic path of length l or a monotone rainbow ...$_{}^{\mathrm{}}$$\mathrm{}_{}^{\mathrm{}}$${}^{\mathrm{}}_{}^{\mathrm{}\mathrm{}}$$_{}^{\mathrm{}\mathrm{}}_{}^{\mathrm{}}$

Motivated by bipartite Gallai–Ramsey type problems, we consider edge-colorings of complete bipartite graphs without rainbow tree and matching. Given two graphs G and H, and a positive integer k, define the bipartite Gallai–Ramsey number bgr k ( G ...

We prove that every P 5-free graph of bounded clique number contains a small hitting set of all its maximum stable sets (where P t denotes the t-vertex path, and for graphs G , H, we say G is H-free if no induced subgraph of G is isomorphic to H)...

This paper deals with the minimum number $m_H(r)$ of edges in an H-free hypergraph with the chromatic number more than r. We show how bounds on Ramsey and Turán numbers imply bounds on $m_H(r)$.

The k-edge-colored bipartite Gallai–Ramsey number bgr k ( G : H ) is defined as the minimum integer n such that n 2 ≥ k and for every N ≥ n, every edge-coloring (using all k colors) of complete bipartite graph K N , N contains a rainbow copy of G ...

For positive integers c and k, we consider the equation L : x + y + c = k z. Two-color Rado number R = R ( c , k ) of L is the least integer, provided that it exists, such that every two-coloring of 1 , 2 , ⋯ , R admits a monochromatic solution ...

The size Ramsey number$\widehat{\text{r}}(G,H)$ of two graphs G, H, introduced by Erdös et al., is defined as $\widehat{\text{r}}(G,H)=min\{|E(F)|:F⟶(G,H)\}$. Recently, Gallai–Ramsey number ${\text{gr}}_k$ has been studied a lot. In this paper, we introduce the concept of size Gallai–Ramsey ...${\stackrel{}{}}_{}$${\stackrel{}{}}_{}$${}_{}$${\stackrel{}{}}_{}$

An r-uniform hypergraph H is semi-algebraic of complexity t = ( d , D , m ) if the vertices of H correspond to points in R d and the edges of H are determined by the sign-pattern of m degree-D polynomials. Semi-algebraic hypergraphs of ...

For fixed nonnegative integers k and $\ell$, the $(P_k,P_{\ell })$-Arrowing problem asks whether a given graph, G, has a red/blue coloring of E(G) such that there are no red copies of $P_k$ and no blue copies of $P_{\ell }$. The problem is trivial when $max(k,\ell )\le 3$, but has ...$\mathrm{}$$$$\mathrm{}$

This paper studies k-claw-free graphs, exploring the connection between an extremal combinatorics question and the power of a convex program in approximating the maximum-weight independent set in this graph class. For the extremal question, we ...

An r-matrix is a matrix with symbols in { 0 , 1 , … , r − 1 }. A matrix is simple if it has no repeated columns. Let F be a finite set of r-matrices. Let forb ( m , r , F ) denote the maximum number of columns possible in a simple r-...

In this paper, we study a Ramsey-type problem for equations of the form a x + b y = p ( z ). We show that if certain technical assumptions hold, then any 2-colouring of the positive integers admits infinitely many monochromatic ...

Given two non-empty graphs G, H and a positive integer k, the Gallai–Ramsey number ${\text{gr}}_k(G:H)$ is defined as the minimum integer N such that for all $n\ge N$, every k-edge-coloring of $K_n$ contains either a rainbow colored copy of G or a monochromatic copy ...${}_{}{}_{\mathrm{}}\mathrm{}$