Vincent Vatter - An Erdős--Hajnal analogue for permutation classes

dmtcs:1328 - Discrete Mathematics & Theoretical Computer Science, March 24, 2016, Vol. 18 no. 2, Permutation Patterns 2015 - https://doi.org/10.46298/dmtcs.1328
An Erdős--Hajnal analogue for permutation classes

Authors: Vincent Vatter

    Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a monotone subsequence of length $cn$.

    https://doi.org/10.46298/dmtcs.1328
    Source: arXiv.org:1511.01076
    Volume: Vol. 18 no. 2, Permutation Patterns 2015
    Section: Permutation Patterns
    Published on: March 24, 2016
    Submitted on: March 24, 2016
    Keywords: Mathematics - Combinatorics
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • The Structure of Permutation Classes; Funder: National Science Foundation; Code: 1301692

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo ARXIV 1910.04813
    Source : ScholeXplorer IsRelatedTo DOI 10.1214/20-aihp1135
    Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1910.04813
    • 10.1214/20-aihp1135
    • 10.1214/20-aihp1135
    • 1910.04813
    • 10.48550/arxiv.1910.04813
    Almost square permutations are typically square

    Share and export

    Consultation statistics

    This page has been seen 607 times.
    This article's PDF has been downloaded 1179 times.