اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Ramsey number of the clique and the hypercube
120
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Ramsey number r(K_s,Q_n) is the smallest positive integer N such that every red-blue colouring of the edges of the complete graph K_N on N vertices contains either a red n-dimensional hypercube, or a blue clique on s vertices. Answering a question of Burr and ErdH{o}s from 1983, and improving on recent results of Conlon, Fox, Lee and Sudakov, and of the current authors, we show that r(K_s,Q_n) = (s-1) (2^n - 1) + 1 for every s in N and every sufficiently large n in N.
قيم البحث
اقرأ أيضاً
Let $q_{min}(G)$ stand for the smallest eigenvalue of the signless Laplacian of a graph $G$ of order $n.$ This paper gives some results on the following extremal problem: How large can $q_minleft( Gright) $ be if $G$ is a graph of order $n,$ with n
o complete subgraph of order $r+1?$ It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on $q_{min}$ are obtained, thus extending previous work of Brandt for regular graphs. In addition, using graph blowups, a general asymptotic result about the maximum $q_{min}$ is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.
The Ramsey number r(K_3,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K_N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and ErdH{o}s conjectured
that r(K_3,Q_n) = 2^{n+1} - 1 for every n in N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K_3,Q_n) le 7000 cdot 2^n. Here we show that r(K_3,Q_n) = (1 + o(1)) 2^{n+1} as n to infty.
We determine the Ramsey number of a connected clique matching. That is, we show that if $G$ is a $2$-edge-coloured complete graph on $(r^2 - r - 1)n - r + 1$ vertices, then there is a monochromatic connected subgraph containing $n$ disjoint copies of
$K_r$, and that this number of vertices cannot be reduced.
There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus in 1965. It is useful in practice if similar results hold for hypergraphs. However the obvious generalization of Motzkin and Strau
s result to hypergraphs is false. Frankl and F{u}redi conjectured that the $r$-uniform hypergraph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-uniform hypergraphs with $m$ edges. For $r=2$, Motzkin and Straus theorem confirms this conjecture. For $r=3$, it is shown by Talbot that this conjecture is true when $m$ is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for $3$-uniform hypergraphs. As an application of this connection, we confirm that Frankl and F{u}redis conjecture holds for bigger ranges of $m$ when $r$=3. We also obtain two weak
Given graphs $G$ and $H$ and a positive integer $q$ say that $G$ is $q$-Ramsey for $H$, denoted $Grightarrow (H)_q$, if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The size-Ramsey number $hat{r}(H)$ of a graph $H$ is
defined to be $hat{r}(H)=min{|E(G)|colon Grightarrow (H)_2}$. Answering a question of Conlon, we prove that, for every fixed $k$, we have $hat{r}(P_n^k)=O(n)$, where $P_n^k$ is the $k$-th power of the $n$-vertex path $P_n$ (i.e. , the graph with vertex set $V(P_n)$ and all edges ${u,v}$ such that the distance between $u$ and $v$ in $P_n$ is at most $k$). Our proof is probabilistic, but can also be made constructive.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
