The van der Waerden complex

Richard Ehrenborg; Likith Govindaiah; Peter S. Park; Margaret Readdy

doi:10.1016/j.jnt.2016.08.012

The van der Waerden complex

Richard Ehrenborg, Likith Govindaiah, Peter S. Park, Margaret Readdy

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We introduce the van der Waerden complex vdW(n,k) defined as the simplicial complex whose facets correspond to arithmetic progressions of length k in the vertex set {1,2,…,n}. We show the van der Waerden complex vdW(n,k) is homotopy equivalent to a CW-complex whose cells asymptotically have dimension at most log⁡k/log⁡log⁡k. Furthermore, we give bounds on n and k which imply that the van der Waerden complex is contractible.

Original language	English
Pages (from-to)	287-300
Number of pages	14
Journal	Journal of Number Theory
Volume	172
DOIs	https://doi.org/10.1016/j.jnt.2016.08.012
State	Published - Mar 1 2017

Bibliographical note

Funding Information:
The authors thank Nigel Pitt for discussions related to asymptotics in Section 3 . The authors also thank the referee for providing the references [1,8,9] . The first author was partially supported by National Security Agency grant H98230-13-1-0280 . This work was partially supported by a grant from the Simons Foundation (# 206001 to Margaret Readdy). The first and fourth authors thank the Princeton University Mathematics Department where this work was initiated.

Publisher Copyright:
© 2016 Elsevier Inc.

Keywords

Arithmetic progressions
Discrete Morse theory
Van der Waerden complex

ASJC Scopus subject areas

Algebra and Number Theory

Access to Document

10.1016/j.jnt.2016.08.012

Cite this

@article{5710762122b04bdb987b75f1eda2fafb,

title = "The van der Waerden complex",

abstract = "We introduce the van der Waerden complex vdW(n,k) defined as the simplicial complex whose facets correspond to arithmetic progressions of length k in the vertex set {1,2,…,n}. We show the van der Waerden complex vdW(n,k) is homotopy equivalent to a CW-complex whose cells asymptotically have dimension at most log⁡k/log⁡log⁡k. Furthermore, we give bounds on n and k which imply that the van der Waerden complex is contractible.",

keywords = "Arithmetic progressions, Discrete Morse theory, Van der Waerden complex",

author = "Richard Ehrenborg and Likith Govindaiah and Park, {Peter S.} and Margaret Readdy",

note = "Funding Information: The authors thank Nigel Pitt for discussions related to asymptotics in Section 3 . The authors also thank the referee for providing the references [1,8,9] . The first author was partially supported by National Security Agency grant H98230-13-1-0280 . This work was partially supported by a grant from the Simons Foundation (# 206001 to Margaret Readdy). The first and fourth authors thank the Princeton University Mathematics Department where this work was initiated. Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2017",

month = mar,

day = "1",

doi = "10.1016/j.jnt.2016.08.012",

language = "English",

volume = "172",

pages = "287--300",

}

TY - JOUR

T1 - The van der Waerden complex

AU - Ehrenborg, Richard

AU - Govindaiah, Likith

AU - Park, Peter S.

AU - Readdy, Margaret

N1 - Funding Information: The authors thank Nigel Pitt for discussions related to asymptotics in Section 3 . The authors also thank the referee for providing the references [1,8,9] . The first author was partially supported by National Security Agency grant H98230-13-1-0280 . This work was partially supported by a grant from the Simons Foundation (# 206001 to Margaret Readdy). The first and fourth authors thank the Princeton University Mathematics Department where this work was initiated. Publisher Copyright: © 2016 Elsevier Inc.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - We introduce the van der Waerden complex vdW(n,k) defined as the simplicial complex whose facets correspond to arithmetic progressions of length k in the vertex set {1,2,…,n}. We show the van der Waerden complex vdW(n,k) is homotopy equivalent to a CW-complex whose cells asymptotically have dimension at most log⁡k/log⁡log⁡k. Furthermore, we give bounds on n and k which imply that the van der Waerden complex is contractible.

AB - We introduce the van der Waerden complex vdW(n,k) defined as the simplicial complex whose facets correspond to arithmetic progressions of length k in the vertex set {1,2,…,n}. We show the van der Waerden complex vdW(n,k) is homotopy equivalent to a CW-complex whose cells asymptotically have dimension at most log⁡k/log⁡log⁡k. Furthermore, we give bounds on n and k which imply that the van der Waerden complex is contractible.

KW - Arithmetic progressions

KW - Discrete Morse theory

KW - Van der Waerden complex

UR - http://www.scopus.com/inward/record.url?scp=84992187987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84992187987&partnerID=8YFLogxK

U2 - 10.1016/j.jnt.2016.08.012

DO - 10.1016/j.jnt.2016.08.012

M3 - Article

AN - SCOPUS:84992187987

VL - 172

SP - 287

EP - 300

ER -

The van der Waerden complex

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this