Results 11 to 20 of about 1,180 (130)
Two extensions of Ramsey’s theorem [PDF]
Duke Mathematical Journal, 2013 Ramsey's theorem, in the version of Erd s and Szekeres, states that every 2-coloring of the edges of the complete graph on {1, 2,...,n} contains a monochromatic clique of order 1/2\log n. In this paper, we consider two well-studied extensions of Ramsey's theorem.
Conlon, David +2 more
openaire +12 more sources
Ramsey's Theorem for Pairs and $k$ Colors as a Sub-Classical Principle of Arithmetic [PDF]
, 2016 The purpose is to study the strength of Ramsey's Theorem for pairs restricted to recursive assignments of $k$-many colors, with respect to Intuitionistic Heyting Arithmetic.
Stefano Berardi, Silvia Steila
openalex +6 more sources
The proof-theoretic strength of Ramsey's theorem for pairs and two colors [PDF]
, 2018 Ramsey's theorem for $n$-tuples and $k$-colors ($\mathsf{RT}^n_k$) asserts that every k-coloring of $[\mathbb{N}]^n$ admits an infinite monochromatic subset.
Ludovic Patey, Keita Yokoyama
openalex +7 more sources
The logical strength of B\"uchi's decidability theorem [PDF]
Logical Methods in Computer Science, 2019 We study the strength of axioms needed to prove various results related to automata on infinite words and B\"uchi's theorem on the decidability of the MSO theory of $(N, {\le})$.
Leszek Kołodziejczyk +3 more
doaj +1 more source
A Ramsey theorem for multiposets [PDF]
European Journal of Combinatorics, 2019 In the parlance of relational structures, the Finite Ramsey Theorem states that the class of all finite chains has the Ramsey property. A classical result of J. Ne et il and V. R dl claims that the class of all finite posets with a linear extension has the Ramsey property. In 2010 M.
Draganić, Nemanja, Mašulović, Dragan
openaire +4 more sources
Separation Property for wB- and wS-regular Languages [PDF]
Logical Methods in Computer Science, 2014 In this paper we show that {\omega}B- and {\omega}S-regular languages satisfy the following separation-type theorem If L1,L2 are disjoint languages of {\omega}-words both recognised by {\omega}B- (resp.
Michał Skrzypczak
doaj +1 more source
Ramsey's theorem and self-complementary graphs [PDF]
, 1972 It is proved that, given any positive integer k, there exists a self-complementary graph with more than 4·214k vertices which contains no complete subgraph with k+1 vertices.
Vašek Chvátal +2 more
openalex +2 more sources
Turán and Ramsey problems for alternating multilinear maps
Discrete Analysis, 2023 Turán and Ramsey problems for alternating multilinear maps, Discrete Analysis 2023:12, 22 pp. Ramsey's theorem (in its finite version) states that for every positive integer $k$ there exists a positive integer $n$ such that every graph with $n$ vertices
Youming Qiao
doaj +1 more source
The weakness of being cohesive, thin or free in reverse mathematics [PDF]
, 2016 Informally, a mathematical statement is robust if its strength is left unchanged under variations of the statement. In this paper, we investigate the lack of robustness of Ramsey's theorem and its consequence under the frameworks of reverse mathematics ...
Patey, Ludovic
core +3 more sources
Open questions about Ramsey-type statements in reverse mathematics [PDF]
, 2015 Ramsey's theorem states that for any coloring of the n-element subsets of N with finitely many colors, there is an infinite set H such that all n-element subsets of H have the same color.
Patey, Ludovic
core +3 more sources