Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
82
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study Ramseys theorem for pairs and two colours in the context of the theory of $alpha$-large sets introduced by Ketonen and Solovay. We prove that any $2$-colouring of pairs from an $omega^{300n}$-large set admits an $omega^n$-large homogeneous set. We explain how a formalized version of this bound gives a more direct proof, and a strengthening, of the recent result of Patey and Yokoyama [Adv. Math. 330 (2018), 1034--1070] stating that Ramseys theorem for pairs and two colours is $forallSigma^0_2$-conservative over the axiomatic theory $mathsf{RCA}_0$ (recursive comprehension).
rate research
Read More
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Let $f(G)$ and $F(G)$ denote the minimum and maximum forcing number of $G$ among all perfect matchings, respectively. Hetyei obtained that the maximum number of edges of graphs $G$ with a unique perfect matching is $n^2$ (see Lov{a}sz [20]). We know that $G$ has a unique perfect matching if and only if $f(G)=0$. Along this line, we generalize the classical result to all graphs $G$ with $f(G)=k$ for $0leq kleq n-1$, and obtain that the number of edges is at most $n^2+2nk-k^2-k$ and characterize the extremal graphs as well. Conversely, we get a non-trivial lower bound of $f(G)$ in terms of the order and size. For bipartite graphs, we gain corresponding stronger results. Further, we obtain a new upper bound of $F(G)$. Finally some open problems and conjectures are proposed.
Let $q$ be a power of a prime $p$, let $k$ be a nontrivial divisor of $q-1$ and write $e=(q-1)/k$. We study upper bounds for cyclotomic numbers $(a,b)$ of order $e$ over the finite field $mathbb{F}_q$. A general result of our study is that $(a,b)leq 3$ for all $a,b in mathbb{Z}$ if $p> (sqrt{14})^{k/ord_k(p)}$. More conclusive results will be obtained through separate investigation of the five types of cyclotomic numbers: $(0,0), (0,a), (a,0), (a,a)$ and $(a,b)$, where $a eq b$ and $a,b in {1,dots,e-1}$. The main idea we use is to transform equations over $mathbb{F}_q$ into equations over the field of complex numbers on which we have more information. A major tool for the improvements we obtain over known results is new upper bounds on the norm of cyclotomic integers.
A set of vertices $Xsubseteq V$ in a simple graph $G(V,E)$ is irredundant if each vertex $xin X$ is either isolated in the induced subgraph $langle Xrangle$ or else has a private neighbor $yin Vsetminus X$ that is adjacent to $x$ and to no other vertex of $X$. The emph{irredundant Ramsey number} $s(m,n)$ is the smallest $N$ such that in every red-blue coloring of the edges of the complete graph of order $N$, either the blue subgraph contains an $m$-element irredundant set or the red subgraph contains an $n$-element irredundant set. The emph{mixed Ramsey number} $t(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ yields an $m$-element irredundant set in the blue subgraph or an $n$-element independent set in the red subgraph. In this paper, we first improve the upper bound of $t(3,n)$; using this result, we confirm that a conjecture proposed by Chen, Hattingh, and Rousseau, that is, $lim_{nrightarrow infty}frac{t(m,n)}{r(m,n)}=0$ for each fixed $mgeq 3$, is true for $mleq 4$. At last, we prove that $s(3,9)$ and $t(3,9)$ are both equal to $26$.
In this paper, we consider a variant of Ramsey numbers which we call complementary Ramsey numbers $bar{R}(m,t,s)$. We first establish their connections to pairs of Ramsey $(s,t)$-graphs. Using the classification of Ramsey $(s,t)$-graphs for small $s,t$, we determine the complementary Ramsey numbers $bar{R}(m,t,s)$ for $(s,t)=(4,4)$ and $(3,6)$.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy of $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
