Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Ramsey number of the clique and the hypercube
95
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 no 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 Straus 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
