Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGrahams Number is Less Than 2^^^6
503
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In [5] Graham and Rothschild consider a geometric Ramsey problem: finding the least n such that if all edges of the complete graph on the points {+1,-1}^n are 2-colored, there exist 4 coplanar points such that the 6 edges between them are monochromatic. They give an explicit upper bound: F(F(F(F(F(F(F(12))))))), where F(m) = 2^^(m)^^3, an extremely fast-growing function. By reducing the problem to a variant of the Hales-Jewett problem, we find an upper bound which is between F(4) and F(5).
rate research
Read More
We prove that there exists an absolute constant $delta>0$ such any binary code $Csubset{0,1}^N$ tolerating $(1/2-delta)N$ adversarial deletions must satisfy $|C|le 2^{text{poly}log N}$ and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants $A$ and $delta>0$ such that any set $Csubset{0,1}^N$ of $2^{log^A N}$ binary strings must contain two strings $c$ and $c$ whose longest common subsequence has length at least $(1/2+delta)N$. As an immediate corollary, we show that $q$-ary codes tolerating a fraction $1-(1+2delta)/q$ of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.
Let $lambda_{2}(G)$ be the second smallest normalized Laplacian eigenvalue of a graph $G$. In this paper, we determine all unicyclic graphs of order $ngeq21$ with $lambda_{2}(G)geq 1-frac{sqrt{6}}{3}$. Moreover, the unicyclic graphs with $lambda_{2}(G)=1-frac{sqrt{6}}{3}$ are also determined.
We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
Let ${rm ex}_{mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${rm ex}_{mathcal{P}}(n,T,H)$ is the well studied function, the planar Turan number of $H$, denoted by ${rm ex}_{mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${rm ex}_{mathcal{P}}(n,C_4)$ and ${rm ex}_{mathcal{P}}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${rm ex}_{mathcal{P}}(n,C_6)leq frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${rm ex}_{mathcal{P}}(n,C_6) leq frac{5}{2}n-7$, for all $ngeq 18$, which improves Lans result. We also pose a conjecture on ${rm ex}_{mathcal{P}}(n,C_k)$, for $kgeq 7$.
Reinhold et al. (Science, 1 May 2020, p. 518) provided two possible interpretations of measurements showing that the Sun is less active than other solar-like stars. We argue that one of those interpretations anticipates the observed differences between the properties of their two stellar samples. This suggests that solar-like stars become permanently less variable beyond a specific evolutionary phase.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
