REVIEW 1 cited by
Fan-complete Ramsey numbers
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
For graphs $G$ and $H$, we consider Ramsey numbers $r(G,H)$ with tight lower bounds, namely, $r(G,H) \geq (\chi(G)-1)(|H|-1)+1,$ where $\chi(G)$ denotes the chromatic number of $G$ and $|H|$ denotes the number of vertices in $H$. We say $H$ is $G$-good if the equality holds. Let $G+H$ be the join graph obtained from graphs $G$ and $H$ by adding all edges between the disjoint vertex sets of $G$ and $H$. Let $nH$ denote the union graph of $n$ disjoint copies of $H$. We show that $K_1+nH$ is $K_p$-good if $n$ is sufficiently large. In particular, the fan-graph $F_n=K_1 + n K_2$ is $K_p$-good if $n\geq 27p^2$, improving previous tower-type lower bounds for $n$ due to Li and Rousseau (1996). Moreover, we give a stronger lower bound inequality for Ramsey number $r(G, K_1+F)$ for the case of $G=K_p(a_1, a_2, \dots, a_p)$, the complete $p$-partite graph with $a_1=1$ and $a_i \leq a_{i+1}$. In particular, using a stability-supersaturation lemma by Fox, He and Wigderson (2021), we show that for any fixed graph $H$, \begin{align*} r(G,K_1+nH) = \left\{ \begin{array}{ll} (p-1)(n |H|+a_2-1)+1 & \textrm{if $n|H|+a_2-1$ is even or $a_2-1$ is even,}\\ (p-1)(n |H|+a_2-2)+1 & \textrm{otherwise,} \end{array} \right. \end{align*} where $G=K_p(1,a_2, \dots, a_p)$ with $a_i$'s satisfying some mild conditions and $n$ is sufficiently large. The special case of $H=K_1$ gives an answer to Burr's question (1981) about the discrepancy of $r(G, K_{1,n})$ from $G$-goodness for sufficiently large $n$. All bounds of $n$ we obtain are not of tower-types.
Forward citations
Cited by 1 Pith paper
-
Fan-goodness of sparse graphs
Sparse connected graphs with at most n(1+1/(204k^3+126k^2)) edges are shown to have Ramsey number 2n-1 against fans F_k, with a similar result for multiple fans.
Discussion (0). Continue with ORCID to comment.