Alphabeta MathHow statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Erdős's finite counting bound for every
Statement
For every natural , the diagonal Ramsey number satisfies
where is The off-diagonal Ramsey number as the least with , for positive , real rational powers are those of Rational powers of a positive base and Monotonicity of and of , and the finite powers and products below use Exponentiation of natural numbers, , and its agreement with the integer power in , The product rule: , and and The sum rule: a finite disjoint union is finite with and , and a sum over a finite index set splits along a partition.
Facts & Assumptions
Given: A natural and ; binomial coefficients are as in The set of -element subsets and the binomial coefficient .
If and are finite, then is finite and (The set of functions between finite sets is finite, with ).
If and , then , equivalently ( for ; hence , the quotient is a natural number, and ).
Every real has a unique integer with (Integer part: for every real there is exactly one integer with ).
Proof
There are edges in , and [L1] therefore counts exactly red-blue edge colourings.
For a fixed -vertex set, exactly colourings make all its edges monochromatic. Summing these finite bad sets over the choices, with overlaps allowed, shows that a colouring with no monochromatic -set exists whenever .
If , then by the definition of the binomial coefficient. If , [L2] gives , so again . Since , the left side in step 2.1 is therefore at most in either case. At this is ; thereafter the ratio of the bound for to that for is . Hence the strict inequality holds for every .
Step 2.1 supplies a colouring on vertices with no monochromatic -set, so . As is an integer and , [L3] implies .
Depends on
- The off-diagonal Ramsey number $R(s,t)$ as the least $N$ with $N\to(s,t)^2$, for positive $s,t$
- The set $[A]^{k}$ of $k$-element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$
- $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$; hence $\binom{n}{k}\,k! = n^{\underline{k}}$, the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$
- The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $\lvert A^{B}\rvert = \lvert A\rvert^{\lvert B\rvert}$
- The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition
- The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$, and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$
- Rational powers $a^r$ of a positive base
- Monotonicity of $r \mapsto a^{r}$ and of $a \mapsto a^{r}$
- Exponentiation of natural numbers, $m^{n}$, and its agreement with the integer power in $\mathbb{R}$
- Integer part: for every real $x$ there is exactly one integer $m$ with $m \le x < m + 1$
Used by
Dependency tree · two levels
69 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- J. Fox et al., Graph Ramsey Theory, Section 2.1 (standard reference, not scraped)