Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process

Authors : Gabriel Istrate, Cosmin Bonchiş

Published in: Combinatorial Pattern Matching

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We investigate partitioning of integer sequences into heapable subsequences (previously defined and established by Byers et al.). We show that an extension of patience sorting computes the decomposition into a minimal number of heapable subsequences (MHS). We connect this parameter to an interactive particle system, a multiset extension of Hammersley’s process, and investigate its expected value on a random permutation. In contrast with the (well studied) case of the longest increasing subsequence, we bring experimental evidence that the correct asymptotic scaling is \(\frac{1+\sqrt{5}}{2}\cdot \ln (n)\). Finally we give a heap-based extension of Young tableaux, prove a hook inequality and an extension of the Robinson-Schensted correspondence.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Dictionary Matching with Uneven Gaps
next chapter The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets
Literature
1.
Aldous, D., Diaconis, P.: Hammersley’s interacting particle process and longest increasing subsequences. Probab. Theory Relat. Fields 103(2), 199–213 (1995)MATHMathSciNetCrossRef
2.
Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Am. Math. Soci. 36(4), 413–432 (1999)MATHMathSciNetCrossRef
3.
Archibald, M., Martínez, C.: The hiring problem and permutations. DMTCS Proc. 01, 63–76 (2009)
4.
Byers, J., Heeringa, B., Mitzenmacher, M., Zervas, G.: Heapable sequences and subseqeuences. In: Proceedings of ANALCO, pp. 33–44 (2011)
5.
Broder, A., Kirsch, A., Kumar, R., Mitzenmacher, M., Upfal, E., Vassilvitskii, S.: The hiring problem and Lake Wobegon strategies. SIAM J. Comput. 39(4), 1233–1255 (2009)MATHMathSciNetCrossRef
6.
7.
Frame, J.S., Robinson, G., Thrall, R.M.: The hook graphs of the symmetric group. Canad. J. Math. 6(316), C324 (1954)MathSciNet
8.
Hammersley, J.M.: A few seedlings of research. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability. Theory of Statistics, vol. 1 (1972)
9.
Hivert, F.: An Introduction to Combinatorial Hopf Algebras Physics and Theoretical Computer Science: From Numbers and Languages to (Quantum) Cryptography Security. IOS Press (2007)
10.
Groenenboom, P.: Hydrodynamical models for analyzing longest increasing sequences. J. Comput. Appl. Math. 142, 83–105 (2002)MathSciNetCrossRef
11.
Istrate, G., Bonchiş, C.: Hammersley’s process with multiple lifelines, and a conjecture on decomposing permutations into heapable sequences (manuscript in preparation, 2015)
12.
13.
Knuth, D.: The Art of Computer Programming. Sorting and Searching, vol. 3. Addison Wesley, Redwood City (1998)
14.
15.
16.
17.
Montoya, L.: A rapidly mixing stochastic system of finite interacting particles on the circle. Stoch. Process. Appl. 67(1), 69–99 (1997)MATHMathSciNetCrossRef
18.
Romik, D.: The Surprising Mathematics of Longest Increasing Sequences. Cambridge University Press, Cambridge (2014)
19.
20.
21.
22.
Vershik, A., Kerov, S.: Asymptotics of Plancherel measure of symmetric group and limit form of Young tables. Dokl. Akad. Nauk SSSR 233(6), 1024–1027 (1977)MathSciNet
Metadata
Title
Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process
Authors
Gabriel Istrate
Cosmin Bonchiş
Copyright Year
2015
Book
Combinatorial Pattern Matching

Print ISBN: 978-3-319-19928-3

Electronic ISBN: 978-3-319-19929-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-19929-0_22

Premium Partner

    Image Credits