Minimum Number of Monotone Subsequences of Length 4 in Permutations

József Balogh; Ping Hu; Bernard Lidický; Oleg Pikhurko; Balázs Udvari; Jan Volec

doi:10.1017/S0963548314000820

Minimum Number of Monotone Subsequences of Length 4 in Permutations

József Balogh, Ping Hu, Bernard Lidický, Oleg Pikhurko, Balázs Udvari, Jan Volec

Mathematics

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

Abstract

We show that for every sufficiently large n, the number of monotone subsequences of length four in a permutation on n points is at least [EQUATION PRESENTED] Furthermore, we characterize all permutations on [n] that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colourings of complete graphs with two colours, where the number of monochromatic K₄ is minimized. We show that all the extremal colourings must contain monochromatic K₄ only in one of the two colours. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.

Original language	English (US)
Pages (from-to)	658-679
Number of pages	22
Journal	Combinatorics Probability and Computing
Volume	24
Issue number	4
DOIs	https://doi.org/10.1017/S0963548314000820
State	Published - Jul 1 2015

ASJC Scopus subject areas

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Online availability

10.1017/S0963548314000820

Library availability

Discover UIUC Full Text

Cite this

@article{9d2a175eeaed41f58e7c793d152e12ea,

title = "Minimum Number of Monotone Subsequences of Length 4 in Permutations",

abstract = "We show that for every sufficiently large n, the number of monotone subsequences of length four in a permutation on n points is at least [EQUATION PRESENTED] Furthermore, we characterize all permutations on [n] that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colourings of complete graphs with two colours, where the number of monochromatic K4 is minimized. We show that all the extremal colourings must contain monochromatic K4 only in one of the two colours. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.",

author = "J{\'o}zsef Balogh and Ping Hu and Bernard Lidick{\'y} and Oleg Pikhurko and Bal{\'a}zs Udvari and Jan Volec",

note = "Publisher Copyright: {\textcopyright} 2014 Cambridge University Press.",

year = "2015",

month = jul,

day = "1",

doi = "10.1017/S0963548314000820",

language = "English (US)",

volume = "24",

pages = "658--679",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Minimum Number of Monotone Subsequences of Length 4 in Permutations

AU - Balogh, József

AU - Hu, Ping

AU - Lidický, Bernard

AU - Pikhurko, Oleg

AU - Udvari, Balázs

AU - Volec, Jan

PY - 2015/7/1

Y1 - 2015/7/1

N2 - We show that for every sufficiently large n, the number of monotone subsequences of length four in a permutation on n points is at least [EQUATION PRESENTED] Furthermore, we characterize all permutations on [n] that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colourings of complete graphs with two colours, where the number of monochromatic K4 is minimized. We show that all the extremal colourings must contain monochromatic K4 only in one of the two colours. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.

AB - We show that for every sufficiently large n, the number of monotone subsequences of length four in a permutation on n points is at least [EQUATION PRESENTED] Furthermore, we characterize all permutations on [n] that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colourings of complete graphs with two colours, where the number of monochromatic K4 is minimized. We show that all the extremal colourings must contain monochromatic K4 only in one of the two colours. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.

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

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

U2 - 10.1017/S0963548314000820

DO - 10.1017/S0963548314000820

M3 - Article

AN - SCOPUS:84939271139

SN - 0963-5483

VL - 24

SP - 658

EP - 679

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 4

ER -

Minimum Number of Monotone Subsequences of Length 4 in Permutations

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this