---
_id: '10055'
abstract:
- lang: eng
  text: "Repeated idempotent elements are commonly used to characterise iterable behaviours
    in abstract models of computation. Therefore, given a monoid M, it is natural
    to ask how long a sequence of elements of M needs to be to ensure the presence
    of consecutive idempotent factors. This question is formalised through the notion
    of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to
    the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains
    k consecutive non-empty factors that correspond to the same idempotent element
    of M. In this work, we study the behaviour of the Ramsey function R_M by investigating
    the regular \U0001D49F-length of M, defined as the largest size L(M) of a submonoid
    of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the
    max operation. We show that the regular \U0001D49F-length of M determines the
    degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications
    of this result, we provide the value of the regular \U0001D49F-length of diverse
    monoids. In particular, we prove that the full monoid of n × n Boolean matrices,
    which is used to express transition monoids of non-deterministic automata, has
    a regular \U0001D49F-length of (n²+n+2)/2."
acknowledgement: This project has received funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
  No. 754411. I wish to thank Michaël Cadilhac, Emmanuel Filiot and Charles Paperman
  for their valuable insights concerning Green’s relations.
alternative_title:
- LIPIcs
article_number: '44'
article_processing_charge: No
author:
- first_name: Ismael R
  full_name: Jecker, Ismael R
  id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  last_name: Jecker
citation:
  ama: 'Jecker IR. A Ramsey theorem for finite monoids. In: <i>38th International
    Symposium on Theoretical Aspects of Computer Science</i>. Vol 187. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2021. doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2021.44">10.4230/LIPIcs.STACS.2021.44</a>'
  apa: 'Jecker, I. R. (2021). A Ramsey theorem for finite monoids. In <i>38th International
    Symposium on Theoretical Aspects of Computer Science</i> (Vol. 187). Saarbrücken,
    Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.STACS.2021.44">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>'
  chicago: Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” In <i>38th International
    Symposium on Theoretical Aspects of Computer Science</i>, Vol. 187. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2021. <a href="https://doi.org/10.4230/LIPIcs.STACS.2021.44">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>.
  ieee: I. R. Jecker, “A Ramsey theorem for finite monoids,” in <i>38th International
    Symposium on Theoretical Aspects of Computer Science</i>, Saarbrücken, Germany,
    2021, vol. 187.
  ista: 'Jecker IR. 2021. A Ramsey theorem for finite monoids. 38th International
    Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical
    Aspects of Computer Science, LIPIcs, vol. 187, 44.'
  mla: Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” <i>38th International
    Symposium on Theoretical Aspects of Computer Science</i>, vol. 187, 44, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2021.44">10.4230/LIPIcs.STACS.2021.44</a>.
  short: I.R. Jecker, in:, 38th International Symposium on Theoretical Aspects of
    Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
  end_date: 2021-03-19
  location: Saarbrücken, Germany
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2021-03-16
date_created: 2021-09-27T14:33:15Z
date_published: 2021-03-10T00:00:00Z
date_updated: 2025-05-14T10:55:11Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.STACS.2021.44
ec_funded: 1
external_id:
  isi:
  - '000635691700044'
file:
- access_level: open_access
  checksum: 17432a05733f408de300e17e390a90e4
  content_type: application/pdf
  creator: cchlebak
  date_created: 2021-10-01T09:55:00Z
  date_updated: 2021-10-01T09:55:00Z
  file_id: '10063'
  file_name: 2021_LIPIcs_Jecker.pdf
  file_size: 720250
  relation: main_file
  success: 1
file_date_updated: 2021-10-01T09:55:00Z
has_accepted_license: '1'
intvolume: '       187'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 38th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  isbn:
  - 978-3-9597-7180-1
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A Ramsey theorem for finite monoids
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 187
year: '2021'
...