Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On uniform relationships between combinatorial problems
HTML articles powered by AMS MathViewer

by François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti and Paul Shafer PDF
Trans. Amer. Math. Soc. 368 (2016), 1321-1359 Request permission

Abstract:

The enterprise of comparing mathematical theorems according to their logical strength is an active area in mathematical logic, with one of the most common frameworks for doing so being reverse mathematics. In this setting, one investigates which theorems provably imply which others in a weak formal theory roughly corresponding to computable mathematics. Since the proofs of such implications take place in classical logic, they may in principle involve appeals to multiple applications of a particular theorem, or to non-uniform decisions about how to proceed in a given construction. In practice, however, if a theorem $\mathsf {Q}$ implies a theorem $\mathsf {P}$, it is usually because there is a direct uniform translation of the problems represented by $\mathsf {P}$ into the problems represented by $\mathsf {Q}$, in a precise sense formalized by Weihrauch reducibility.

We study this notion of uniform reducibility in the context of several natural combinatorial problems, and compare and contrast it with the traditional notion of implication in reverse mathematics. We show, for instance, that for all $n,j,k \geq 1$, if $j < k$, then Ramsey’s theorem for $n$-tuples and $k$ many colors is not uniformly, or Weihrauch, reducible to Ramsey’s theorem for $n$-tuples and $j$ many colors. The two theorems are classically equivalent, so our analysis gives a genuinely finer metric by which to gauge the relative strength of mathematical propositions.

We also study Weak König’s Lemma, the Thin Set Theorem, and the Rainbow Ramsey’s Theorem, along with a number of their variants investigated in the literature. Weihrauch reducibility turns out to be connected with sequential forms of mathematical principles, where one wishes to solve infinitely many instances of a particular problem simultaneously. We exploit this connection to uncover new points of difference between combinatorial problems previously thought to be more closely related.

References
Similar Articles
Additional Information
  • François G. Dorais
  • Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755-3551
  • Email: francois.g.dorais@dartmouth.edu
  • Damir D. Dzhafarov
  • Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
  • MR Author ID: 781680
  • ORCID: 0000-0003-4921-7561
  • Email: damir@math.uconn.edu
  • Jeffry L. Hirst
  • Affiliation: Department of Mathematical Sciences, Appalachian State University, Boone, North Carolina 28608-2092
  • MR Author ID: 242430
  • ORCID: 0000-0002-8273-8951
  • Email: jlh@math.appstate.edu
  • Joseph R. Mileti
  • Affiliation: Department of Mathematics and Statistics, Grinnell College, Grinnell, Iowa 50112
  • Email: miletijo@grinnell.edu
  • Paul Shafer
  • Affiliation: Department of Mathematics, Ghent University, Ghent, Belgium
  • MR Author ID: 920651
  • ORCID: 0000-0001-5386-9218
  • Email: paul.shafer@ugent.be
  • Received by editor(s): October 30, 2012
  • Received by editor(s) in revised form: December 2, 2013, and March 16, 2014
  • Published electronically: April 9, 2015
  • Additional Notes: The second author was partially supported by an NSF Postdoctoral Fellowship
    The third author was partially supported by grant ID#20800 from the John Templeton Foundation. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation
    The fifth author was supported by the Fondation Sciences Mathématiques de Paris and is also an FWO Pegasus Long Postdoctoral researcher
  • © Copyright 2015 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 368 (2016), 1321-1359
  • MSC (2010): Primary 03B30, 05D10; Secondary 05D40, 05D15, 03D32, 03D80, 03F35
  • DOI: https://doi.org/10.1090/tran/6465
  • MathSciNet review: 3430365