Asymptotic enumeration of non-crossing partitions on surfaces

ASYMPTOTIC ENUMERATION OF NON-CROSSING PARTITIONS ON SURFACES? JUANJO RU´ E, IGNASI SAU, AND DIMITRIOS M. THILIKOS Abs ac . We gene alize he no ion o non-c ossing pa i ion on a disk o gene al su aces wi h bounda y. Fo his, we conside a su ace Σ and in oduce he numbe CΣ(n) o non- c ossing pa i ions o a se o npoin s laying on he bounda y o Σ. Ou main esul is an asymp o ic es ima e o CΣ(n). The p oo s use bijec i e echniques a ising om map enume a ion, join wi h he symbolic me hod and singula i y analysis on gene a ing unc ions. An ou come o ou esul s is ha he exponen ial g ow h o CΣ(n) is he same as he one o he n- h Ca alan numbe , i.e., does no change when we mo e om he case whe e Σ is a disk o gene al su aces wi h bounda y. 1. In oduc ion In combina o ics, a non-c ossing pa i ion o size nis a pa i ion o he se {1,2, . . . , n} wi h he ollowing p ope y: i 1 ≤a < b < c < d ≤nand a subse o he non-c ossing pa i ion con ains aand c, hen no o he subse con ains bo h band d. One can ep esen such a pa i ion on a disk by placing npoin s on he bounda y o he disk, labeled in cyclic o de , and d awing each subse as a con ex polygon (also called block) on he poin s belonging o he subse . Then, he non-c ossing condi ion is equi alen o he ac ha he d awing is plane and he blocks a e pai wise disjoin . These combina o ial objec s a e impo an in many aspec s, see o ins ance [8, 18]. The enume a ion o non-c ossing pa i ions o size nis one o he i s non i ial p oblems in enume a i e combina o ics: i is well-known ha he numbe o hese s uc u es (ei he by using di ec oo decomposi ions [9] o bijec i e a gumen s [19]) co esponds o Ca alan numbe s. Mo e conc e ely, he numbe o non-c ossing pa i ions o {1,2, . . . , n}on a disk is equal o he Ca alan numbe C(n) = 1 n+1 2n n. This pape deals wi h a gene aliza ion o he no ion o non-c ossing pa i ion on su aces o highe genus wi h bounda y, ei he o ien able o no . In he elemen a y case whe e Σ is a disk, he enume a ion o non-c ossing pa i ions can be di ec ly educed by bijec i e a gumen s o he map enume a ion amewo k (all pa i ions can be ealized geome ically in such a way ha egions a e con ac ible). The e o e, in his case CΣ(n) is he n- h Ca alan numbe . Howe e , o gene alize he no ion o non-c ossing pa i ion o su aces o highe genus is no s aigh o wa d and needs o be de ined p ope ly (see Sec ion 3). In pa icula we a e in e es ed in non-c ossing pa i ions o se s o size n, namely he o al numbe o e ices o e all he bounda y componen s is equal o n. Addi ionally, hese e ices a e ma ked in he way ha is desc ibed in Sec ion 3. The main di icul y is ha he e is no bijec ion be ween non-c ossing pa i ions o a se o size non a su ace Σ and i s geome ic ep esen a ion, which ?Mos o he esul s o his pape we e announced in he ex ended abs ac “Dynamic p og amming o g aphs on su aces. P oc. o ICALP’2010, olume 6198 o LNCS, pages 372-383”, which is a combina ion o an algo i hmic amewo k (whose ull e sion can be ound in [16]) and he enume a i e esul s p esen ed in his pape . The i s au ho is suppo ed by he Eu opean Resea ch Council unde he Eu opean Communi y’s 7 h F amewo k P og amme, ERC g an ag eemen no 208471 - Explo eMaps p ojec . The second au ho is suppo ed by F ench p ojec s AGAPE (ANR-09-BLAN-0159) and GRATOS (ANR-09-JCJC-0041-01). The hi d au ho was Co- inanced by he Eu opean Union (Eu opean Social Fund - ESF) and G eek na ional unds h ough he Ope a ional P og am “Educa ion and Li elong Lea ning” o he Na ional S a egic Re e ence F amewo k (NSRF) - Resea ch Funding P og am: “Thales. In es ing in knowledge socie y h ough he Eu opean Social Fund”. 1 2 J. RU´ E, I. SAU, AND D. M. THILIKOS means ha he same non-c ossing pa i ion can a ise om di e en geome ic ep esen a ions (see Figu e 10 o an example). In his pape , we s udy enume a i e p ope ies o hese geome ic ep esen a ions. F om his s udy we deduce asymp o ic es ima es o he subjacen non-c ossing pa i ions o e e y su ace Σ. The main esul o his pape is he ollowing: le Σ be a su ace wi h Eule cha ac e is ic χ(Σ) and whose bounda y has β(Σ) connec ed componen s. Then he numbe o non-c ossing pa i ions on Σ, CΣ(n) = |ΠΣ(n)|, o nla ge enough, e i ies he asymp o ic uppe bound (1) |ΠΣ(n)| ≤ c(Σ) Γ (−3/2χ(Σ) + β(Σ))n−3/2χ(Σ)+β(Σ)−14n, whe e c(Σ) is a unc ion depending only on Σ ( o a bound on c(Σ), see Sec ion 5), and Γ is he Gamma unc ion: Γ(u) = R∞ 0 u−1e− d . This uppe bound, oge he wi h he ac ha e e y non-c ossing pa i ion on a disk admi s a ealiza ion on Σ (and consequen ly C(n)≤CΣ(n)), gi es he esul lim n→∞CΣ(n)1/n = lim n→∞C(n)1/n = 4.(2) In o he wo ds, CΣ(n) has he same exponen ial g ow h as he Ca alan numbe s, no ma e he su ace Σ. In o de o ge he uppe bound (1), we a gue in h ee le els: we s a om a opological le el, s a ing he p ecise de ini ions o he objec s we wan o s udy, and showing ha we can es ic ou sel es o he s udy o hype maps and bipa i e maps [5]. Once we es ic ou sel es o he map enume a ion amewo k, we use he main ideas o [2] in o de o ob ain combina o ial decomposi ions o he dual maps o he objec s unde s udy (see also [3, 4]). Finally, once we ha e explici exp essions o he gene a ing unc ions o hese combina o ial amilies, we s udy gene a ing unc ions ( o mal powe se ies) as analy ic objec s. In he analy ic s ep, we ex ac singula expansions o he coun ing se ies om he esul ing gene a ing unc ions. We de i e asymp o ic o mulas om hese singula expansions by ex ac ing coe icien s, using he T ans e Theo ems o singula i y analysis [11, 10]. The asymp o ic analysis ca ied ou in his pape has impo an consequences in he design o algo i hms o g aphs on su aces: he enume a ion o non-c ossing pa i ions has been used in [16] o build a amewo k o he design o 2O(k)·nO(1) s ep dynamic p og amming algo i hms o sol e a b oad class o NP-ha d op imiza ion p oblems o su ace-embedded g aphs on n e ices o b anchwid h a mos k. The app oach is based on a new ype o b anch decomposi ion called su ace cu decomposi ion, which gene alizes sphe e cu decomposi ions o plana g aphs in oduced by Seymou and Thomas [17] (see also [7]) and whe e dynamic p og amming should be applied o each pa icula p oblem. Mo e p ecisely, he use o su ace cu decomposi ions yields algo i hms wi h unning imes wi h a single-exponen ial dependence on b anchwid h, and allows o uni y and imp o e all p e ious esul s in his ac i e ield o pa ame e ized complexi y [6, 7, 16]. The key idea is ha he size o he ables o a dynamic p og amming algo i hm o e a su ace cu decomposi ion can be uppe -bounded in e ms o he non-c ossing pa i ions on su aces wi h bounda y. See [16] o mo e de ails and e e ences. Ou line o he pape . In Sec ion 2 we include all he de ini ions and he equi ed backg ound conce ning opological su aces, maps on su aces, he symbolic me hod in combina o ics, and he singula i y analysis on gene a ing unc ions. In Sec ion 3 we s a e he p ecise de ini ion o non-c ossing pa i ion on a gene al su ace, as well as he connec ion wi h he map enume a ion amewo k. Uppe bounds o he numbe o non-c ossing pa i ions on a su ace Σ wi h bounda y a e ob ained in Sec ion 4, and he main esul is p o ed. A mo e de ailed s udy o he cons an c(Σ) o Equa ion (1) is done in Sec ion 5. 2. Backg ound and de ini ions In his sec ion we s a e all he necessa y de ini ions and esul s needed in he sequel. In Subsec ion 2.1 we s a e he main esul s conce ning opological su aces, and in Subsec ion 2.2 we ecall he basic de ini ions abou maps on su aces. Finally, in Subsec ion 2.3 we make a b ie ASYMPTOTIC ENUMERATION OF NON-CROSSING PARTITIONS ON SURFACES 3 summa y o he symbolic me hod in combina o ics, as well as he basic echniques in singula i y analysis on gene a ing unc ions. 2.1. Topological su aces. In his wo k, su aces a e compac (hence closed and bounded) and hei bounda y is homeomo phic o a ini e se (possibly emp y) o disjoin simple ci cles. We deno e by β(Σ) he numbe o connec ed componen s o he bounda y o a su ace Σ. The Su ace Classi ica ion Theo em [15] asse s ha a compac and connec ed su ace wi hou bounda y is de e mined, up o homeomo phism, by i s Eule cha ac e is ic χ(Σ) and by i s o ien abili y. Mo e p ecisely, o ien able su aces a e ob ained by adding g≥0handles o he sphe e S2, ob aining a su ace wi h Eule cha ac e is ic 2 −2g. Non-o ien able su aces a e ob ained by adding h > 0c oss-caps o he sphe e, ge ing a non-o ien able su ace wi h Eule cha ac e is ic 2−h. Gi en a su ace wi h bounda y Σ, we deno e by Σ he su ace (wi hou bounda y) ob ained om Σ by gluing a disk on each o he β(Σ) componen s o he bounda y o Σ. I is hen easy o show ha χΣ=β(Σ) + χ(Σ). In o he wo ds, su aces unde s udy a e de e mined, up o homeomo phism, by hei o ien abili y, hei Eule cha ac e is ic, and he numbe o connec ed componen s o hei bounda y. Acycle on Σ is a opological subspace o Σ which is homeomo phic o a ci cle. We say ha a cycle S1sepa a es Σ i Σ S1has wo connec ed componen s. The ollowing esul conce ning a sepa a ing cycle is an immedia e consequence o P oposi ion 4.2.1 in [15]. Lemma 2.1.1. Le Σbe a su ace wi h bounda y and le S1be a sepa a ing cycle on Σ. Le V1and V2be connec ed su aces ob ained by cu ing Σalong S1and gluing a disk on he newly c ea ed bounda ies. Then χ(Σ) = χ(V1) + χ(V2)−2. 2.2. Maps on su aces and duali y. Ou main e e ence o maps is he monog aph o Lando and Z onkin [14]. A map on Σ is a pa i ion o Σ in o ze o, one, and wo dimensional se s homeomo phic o ze o, one and wo dimensional open disks, espec i ely (in his o de , e ices, edges, and aces). The se o e ices, edges, and aces o a map Mis deno ed by V(M), E(M), and F(M), espec i ely. We use (M), e(M), and (M) o deno e |V(M)|,|E(M)|, and |F(M)|, espec i ely. The deg ee d( ) o a e ex is he numbe o edges inciden wi h , coun ed wi h mul iplici y (loops a e coun ed wice). An edge o a map has wo ends (also called hal -edges), and ei he one o wo sides, depending on he numbe o aces which is inciden wi h. A map is oo ed i an edge and one o i s hal -edges and sides a e dis inguished as he oo - edge, oo -end, and oo -side, espec i ely. This de ini ion is equi alen o ma king a co ne o he skele on o he objec . Obse e ha oo ing on o ien able su aces usually omi s he choice o a oo -side because he subjacen su ace ca ies a global o ien a ion, and maps a e conside ed up o o ien a ion-p ese ing homeomo phism. Ou choice o a oo -side is equi alen in he o ien able case o he choice o an o ien a ion o he su ace. The oo -end and -sides de ine he oo - e ex and - ace, espec i ely. Roo ed maps a e conside ed up o cell-p ese ing homeomo phisms p ese ing he oo -edge, -end, and -side. In igu es, he oo -edge is indica ed as an o ien ed edge poin ing away om he oo -end and c ossed by an a ow poin ing owa ds he oo -side ( his las , p o ides he o ien a ion o he su ace). Fo a map M, he Eule cha - ac e is ic o M, which is deno ed by χ(M), is he Eule cha ac e is ic o he unde lying su ace. Duali y. Gi en a map Mon a su ace Σ wi hou bounda y, he dual map o M, which we deno e by M∗, is a map on Σ ob ained by d awing a e ex o Min each ace o Mand an edge o Mac oss each edge o M. I he map Mis oo ed, he oo -edge eo Mis de ined in he na u al way: he oo -end and oo -side o Mco espond o he side and end o ewhich a e no he oo -side and oo -end o M, espec i ely. This cons uc ion can be gene alized o su aces wi h bounda y in he ollowing way: o a map Mon a su ace Σ wi h bounda y, no ice ha he ( oo ed) map Mde ines a ( oo ed) map Mon Σ by gluing a disk (which becomes a ace o M) along each bounda y componen o Σ. We call hese aces o Mex e nal. Then he usual cons uc ion o he dual map M∗applies using he ex e nal aces. The dual o a map Mon a su ace Σ wi h bounda y is he map on Σ, deno ed by M∗, cons uc ed om M∗by spli ing each ex e nal e ex o M∗( ha is, e ices associa ed o ex e nal aces). 4 J. RU´ E, I. SAU, AND D. M. THILIKOS The new e ices ha a e ob ained a e called dangling lea es, which ha e deg ee one. Obse e ha we can econs uc he map M om M∗, by pas ing he dangling lea es inciden wi h he same ace, and applying duali y. An example o his cons uc ion is shown in Figu e 1. Figu e 1. A map wi h bounda y and i s dual. 2.3. The symbolic me hod and analy ic combina o ics. Ou main e e ence in enume a- i e combina o ics is he book o Flajole and Sedgewick [11]. The amewo k in oduced in his book gi es a language o ansla e combina o ial condi ions be ween combina o ial classes in o equa ions ela ing he associa ed gene a ing unc ions. This is wha is called he symbolic me hod in combina o ics. La e , we can ea hese equa ions as ela ions be ween analy ic unc ions. This poin o iew gi es he possibili y o use complex analysis echniques o ob ain in o ma ion abou he combina o ial classes. This is he o igin o he e m analy ic combina o ics. The symbolic me hod. Fo a se Ao objec s, le |·| be an applica ion (called size) om A o N. We assume ha he numbe o elemen s in Awi h a ixed size is always ini e. A pai (A,|·|) is called a combina o ial class. Unde hese assump ions, we de ine he o mal powe se ies (called he gene a ing unc ion o GF associa ed wi h he class) A(x) = Pa∈A x|a|=P∞ n=0 anxn. Con e sely, we w i e an= [xn]A(x). The symbolic me hod p o ides a di ec way o ansla e combina o ial cons uc ions be ween combina o ial classes in o equa ions be ween GFs. The cons uc ions we use in his wo k and hei ansla ion in o he language o GFs a e shown in Table 1. Cons uc ion GF Union A∪B A(x) + B(x) P oduc A×B A(x)B(x) Sequence Seq (A)1 1−A(x) Poin ing A•x∂ ∂x A(x) Table 1. Cons uc ions and ansla ions in o GFs. The union A∪Bo Aand B e e s o he disjoin union o he classes. The ca esian p oduc A×B o Aand Bis he se {(a, b) : a∈ A, b ∈ B}. The sequence Seq (A) o a se Aco esponds o he se E ∪ A ∪ (A×A)∪(A×A×A)∪. . ., whe e Edeno es he emp y se . A las , he poin ing ope a o A•o a se Aconsis s in poin ing one o he a oms o each elemen a∈ A. No ice ha in he sequence cons uc ion, he exp ession E ∪ A∪(A×A)∪(A×A×A)∪. . . ansla es in o P∞ k=0 A(x)k, which is a sum o a geome ic se ies. In he case o poin ing, no e also ha x∂ ∂z A(x) = Pn>0nanxn. ASYMPTOTIC ENUMERATION OF NON-CROSSING PARTITIONS ON SURFACES 5 Singula i y analysis. The s udy o he asymp o ic g ow h o he coe icien s o GFs can be ob ained by conside ing GFs as complex unc ions analy ic a ound z= 0. This is he main idea o analy ic combina o ics. The g ow h beha io o he coe icien s depends only on he smalles posi i e singula i y o he GF. I s loca ion p o ides he exponen ial g ow h o he coe icien s, and i s beha io gi es he subexponen ial g ow h o he coe icien s. Mo e conc e ely, o eal numbe s R > ρ > 0 and 0 < φ < π/2, le ∆ρ(φ, R) be he se {z∈C:|z|< R, z 6=ρ, |A g(z−ρ)|> φ}. We call a se o his ype a den ed domain o a domain den ed a ρ. Le A(z) and B(z) be GFs whose smalles singula i y is he eal numbe ρ. We w i e A(z)∼z→ρB(z) i limz→ρA(z)/B(z) = 1. We ob ain he asymp o ic expansion o [zn]A(z) by ans e ing he beha io o A(z) a ound i s singula i y om a simple unc ion B(z), om which we know he asymp o ic beha io o hei coe icien s. This is he main idea o he so-called T ans e Theo ems de eloped by Flajole and Odlyzko [10]. These esul s allow us o deduce asymp o ic es ima es o an analy ic unc ion using i s asymp o ic expansion nea i s dominan singula i y. In ou wo k we use a mix u e o Theo ems VI.1 and VI.3 om [11]: P oposi ion 2.3.1 (T ans e Theo em).I A(z)is analy ic in a den ed domain ∆=∆ρ(φ, R), whe e ρis unique singula i y wi h smalles modulo o A(z), and A(z)∼ z∈∆,z→ρc·1−z ρ−α +O 1−z ρ−α+γ!, o α6∈ {0,−1,−2, . . .}, and γ > 0 hen (3) an=c·nα−1 Γ(α)·ρ−n1 + O(n−γ), whe e Γis he Gamma unc ion: Γ(u) = R∞ 0 u−1e− d . 3. Non-c ossing pa i ions on su aces wi h bounda y In his sec ion we in oduce he p ecise de ini ion o a non-c ossing pa i ion on a su ace wi h bounda y. The no ion o a non-c ossing pa i ion on a gene al su ace is no as simple as in he case o a disk, and mus be s a ed in e ms o objec s mo e gene al han maps. Ou s a egy o ob ain asymp o ic es ima es o he numbe o non-c ossing pa i ions on su aces consis s o showing ha we can es ic ou sel es o he s udy o ce ain amilies o maps. Mo e conc e ely, we show ha he s udy o non-c ossing pa i ions is a pa icula case o he s udy o hype maps [5], which can be in e p e ed as bipa i e maps. The plan o his sec ion is he ollowing: in Subsec ion 3.1 we se up ou no a ion and we de ine a non-c ossing pa i ion on a gene al su ace. In Subsec ion 3.2 we show ha we can es ic ou sel es o he s udy o bipa i e maps in which e ices belong o he bounda y o he su ace. 3.1. Bipa i e subdi isions and non-c ossing pa i ions. Le Σ be a connec ed su ace wi h bounda y, and le S1 1,S1 2,...,S1 β(Σ) be he connec ed componen s o i s bounda y. Fo 1≤ ≤β(Σ), we deno e by V ={1 ,2 , . . . , m }a se o e ices o e S1 , and |V |=n . We assume ha he e exis s a o al numbe o n e ices on he bounda y o Σ, hence n1+··· + nβ(Σ) =n. Obse e ha e ices a e dis ibu ed among all he componen s o he bounda y o Σ. In pa icula , i is possible ha a bounda y componen is no inciden wi h any e ex. Ve ices on each bounda y componen a e labeled in coun e clockwise o de . In pa icula , bounda y componen s a e dis inguishable. Obse e ha an equi alen way o label hese e ices is dis inguishing on each bounda y componen an edge- oo , whose ends a e e ices 1 and 2 . Hence, e e y connec ed componen o he bounda y o Σ is edge- oo ed in coun e clockwise o de . Abipa i e subdi ision wi h n e ices So Σ is a decomposi ion o Σ (up o homeomo phisms o he su ace) in o ze o-, one-, and wo-dimensional open and connec ed subse s, whe e he se o e ices is equal o V1∪ ··· ∪ Vβ(Σ), and he e is a p ope wo-colo ing (namely, using black and whi e colo s) o he wo-dimensional egions, in such a way ha each e ex appea s (possibly mo e han once) in he bounda y o a unique black egion. We also demand ha he 6 J. RU´ E, I. SAU, AND D. M. THILIKOS in e sec ion o he e ex se and he bounda y o each black egion con ains a leas one e ex. See Figu e 2 o examples o geome ic ep esen a ions o bipa i e subdi isions on di e en su aces wi h bounda y. Figu e 2. Geome ic ep esen a ion o non-c ossing pa i ions on a disk, on a cylinde , and on a M¨obius band. In gene al, a bipa i e subdi ision is no a map, as wo-dimensional egions migh no be con ac ible. Gi en a bipa i e subdi ision, we de ine i s blocks as he closu es o i s black aces. The size o a block is he numbe o e ices appea ing on i s bounda y, coun ing mul iple appea ances only once. A block o size kis egula i i is inciden wi h exac ly k e ices (namely, he con ou walk along he bo de o he block mee s each e ex exac ly once) and i is con ac ible (i.e., homeomo phically equi alen o a disk). A bipa i e subdi ision is egula i each block is egula . A bipa i e subdi ision is i educible i i is egula and all i s whi e aces a e con ac ible. We deno e by SΣ(n), RΣ(n), and PΣ(n) he se o gene al, egula , and i educible bipa i e subdi isions wi h n e ices o Σ, espec i ely. See Figu e 3 o examples o bipa i e subdi isions. In pa icula , he da ke blocks in he i s bipa i e subdi ision a e no egula . Figu e 3. Th ee bipa i e subdi isions S1, S2, and S3.S2is egula bu no i educible, while S3is i educible. Le Sbe a bipa i e subdi ision o Σ wi h n e ices and le X1, . . . , Xsbe he se o i s blocks. Clea ly, hese blocks de ine he pa i ion πΣ(S) o he e ex se V1∪ ··· ∪ Vβ(Σ). We say ha a pa i ion o he e ex se is non-c ossing on a su ace Σ i i is equal o πΣ(S) o a ce ain bipa i e subdi ision So Σ. A non-c ossing pa i ion is said o be egula (o i educible) i i a ises om a egula (o i educible) bipa i e subdi ision. Obse e ha his de ini ion gene alizes he no ion o a non-c ossing pa i ion on a disk. We de ine ΠΣ(n) as he se o non-c ossing pa i ions o Σ wi h n e ices and we se CΣ(n) = |ΠΣ(n)|. ASYMPTOTIC ENUMERATION OF NON-CROSSING PARTITIONS ON SURFACES 7 3.2. Reduc ion o he map amewo k. In his subsec ion we show ha we can es ic ou sel es o he s udy o bipa i e maps in which e ices belong o he bounda y o he su ace. La e , his educ ion allow us o s udy non-c ossing pa i ions in he con ex o map enume a ion. Le Σ1and Σ2be su aces wi h bounda y. We w i e Σ2⊂Σ1i he e exis s a con inuous injec ion i: Σ2,→Σ1such ha i(Σ2) is homeomo phic o Σ2(in pa icula , he image by io he bounda y o Σ2is con ained in he bounda y o Σ1). I Sis a bipa i e subdi ision o Σ2and Σ2⊂Σ1, hen he injec ion iinduces a bipa i e subdi ision i(S) on Σ1such ha πΣ2(S) = πΣ1(i(S)). Roughly speaking, all bipa i e subdi isions on Σ2can be ealized on a su ace Σ1which con ains Σ2. One can w i e hen ha ΠΣ2(n)⊆ΠΣ1(n) i Σ2⊂Σ1, and hen i holds ha |ΠΣ2(n)|≤|ΠΣ1(n)|. This p o es he i ial bound C(n)≤ |ΠΣ(n)| o all choices o Σ. As he ollowing lemma shows, egula i y is p ese ed by injec ions o su aces. Lemma 3.2.1. Le M1be a egula bipa i e subdi ision o Σ1, and le Σ1⊂Σ. Then M1de ines a egula bipa i e subdi ision Mo e Σsuch ha πΣ1(M1) = πΣ(M). P oo . Le i: Σ1,→Σ be he co esponding injec i e applica ion, and conside M=i(M1). In pa icula , a block Xo M1is opologically equi alen o he block i(X): iis a homeomo phism be ween Σ and i(Σ). Hence i(X) is egula ( his is easily e i ied: i he size o Xis equal o k, hen i(X) is con ac ible and i s closu e in e sec s he bounda y exac ly in kpoin s, hence i is egula ) and Mis egula .  The ollowing p oposi ion allows us o educe he p oblem o he s udy o egula bipa i e subdi isions. P oposi ion 3.2.2. Le S∈ SΣ(n)be a bipa i e subdi ision o Σand le πΣ(S)be he associa ed non-c ossing pa i ion on Σ. Then, he e exis s a egula bipa i e subdi ision R∈ RΣ(n)such ha πΣ(R) = πΣ(S). P oo . Le Xbe a block o So size k. I Xis no egula , hen ei he i s bounda y mee s a leas one e ex se e al imes o Xis no con ac ible. We show ha , in each o he p e ious cases, we can apply local ope a ions – ha may simpli y he su ace– and ans o m Xin o a new block wi h he same e ices. Hence he associa ed non-c ossing pa i ion emains he same. Assume ha he i s case happens. Le be a e ex inciden se e al imes wi h X. In his case we de ine he ope a ion o cu ing a e ex as ollows: conside he in e sec ion o a small ball o adius ε > 0 cen e ed a wi h he block X, namely Bε( )∩X. Obse e ha (Bε( )∩X) { } has se e al connec ed componen s ( he same as he numbe o imes he closu e o Xin e sec s ). We de ine he new block by de o ming all excep one o hese componen s in such a way ha hey do no in e sec he bounda y o Σ. Nex , we pas e he e ex o he unique componen which has no been de o med (see Figu e 4). Then he esul ing bipa i e subdi ision has he same associa ed non-c ossing pa i ion, and is inciden wi h he co esponding block exac ly once. Applying his a gumen o each e ex o Xwe ge a block which is inciden once (as we mo e along i s bo de ) wi h e e y one o he e ices which de ine i . Figu e 4. The ope a ion o cu ing he e ex . Applying his ope a ion a mos n imes he esul ing block in e sec s each e ex ei he one o ze o imes. We can apply hen his ope a ion o all he blocks. Wi hou loss o gene ali y, using his ope a ion he numbe o imes needed, we can assume ha ou ini ial bipa i e subdi ision sa is ies ha each e ex appea s a mos once on he bounda y o a block. Assume now ha Xis a non-con ac ible block o S. Le S1 Xbe a non-con ac ible cycle con ained in X. Two si ua ions may happen: ei he X S1 Xis connec ed o disconnec ed. We analyze bo h cases. 8 J. RU´ E, I. SAU, AND D. M. THILIKOS Assume i s ha S1 Xdisconnec s X. We may assume ha each componen con ains, a leas , one bounda y componen (i no , he co esponding connec ed componen o X S1 Xcould be subs i u ed by a disk). In pa icula , in oking he Jo dan’s cu e Theo em, he e exis s a pai o e ices in each connec ed componen (and also he co esponding bounda y componen s whe e hese e ices belong). We de ine he ope a ion o joining bounda ies in he ollowing way (see Figu e 5 in o de o cla i y his cons uc ion): we conside a pa h be ween hese wo e ices (in Figu e 5 i is he line joining he wo e ices). This pa h exis s as Xis a connec ed open subse o Σ. Conside also wo new pa hs inside X ha join hese wo e ices a ound he ini ial pa h. We hen de ine a new block X0by dele ing om X he open egion de ined by hese wo pa hs ( he egion which con ains he ini ial pa h be ween he wo e ices). Figu e 5. The ope a ion o joining bounda ies. Applying he cu e ex ope a ion o e hese wo e ices we ge a new block X00, and he non-c ossing pa i ion associa ed wi h his new bipa i e subdi ision is he same as he ini ial one. Obse e ha he e does no exis a cycle which disconnec s he block in such a way ha he conside ed bounda y componen s lay, each o hem, in a di e en connec ed componen . As he numbe o bounda y componen s is ini e, we can apply hese ope a ions a ini e numbe o imes in o de o ge a new block wi hou sepa a ing cycles. Suppose now ha X S1 Xis connec ed. We cu he su ace along S1 Xand we pas e ei he a disk o a pai o disks along i s bo de , depending on whe he S1 Xis one- o wo-sided on Σ. This ope a ion dec eases he genus o he su ace and does no al e he e ices inciden wi h he block (as he ope a ion does no change he se o e ices me by each block). As he genus o he su ace is bounded, we can apply his ope a ion a ini e numbe o imes un il he esul ing block becomes con ac ible. To conclude, a e con e ing each block o a egula one, he esul ing su ace is Σ1⊂Σ. The esul ing bipa i e subdi ision S0on Σ1is egula (since all he blocks a e egula ), and hen by Lemma 3.2.1 he e exis s a egula bipa i e subdi ision Ro e Σ such ha πΣ(R) = πΣ1(M0), as claimed.  No ice ha om P oposi ion 3.2.2 we also see ha |ΠΣ(n)| ≤ |RΣ(n)|.(4) In he nex sec ion we educe ou s udy o he amily o i educible bipa i e subdi isions. This pe mi s us o uppe -bound |PΣ(n)|ins ead o dealing wi h he mo e complica ed ask o uppe - bounding |RΣ(n)|. The eason why his also gi es an asymp o ic bound o |ΠΣ(n)|is ha he sub amily PΣ(n) p o ides he main con ibu ion o he asymp o ic es ima es o RΣ(n). 4. Uppe bounds o non-c ossing pa i ions on su aces The plan o his sec ion is he ollowing: in Subsec ion 4.1 we in oduce amilies o plane ees ha a ise by duali y on non-c ossing pa i ions on a disk. These combina o ial s uc u es a e used in Subsec ion 4.2 o ob ain a ee-like decomposi ion which p o ides a way o ob ain asymp o ic es ima es o he numbe o i educible bipa i e subdi isions o Σ wi h n e ices, namely |PΣ(n)|. These asymp o ic es ima es a e ound in Subsec ion 4.3 o i educible bipa - i e subdi isions. Finally, we p o e in Subsec ion 4.4 ha he numbe o i educible bipa i e ASYMPTOTIC ENUMERATION OF NON-CROSSING PARTITIONS ON SURFACES 9 subdi isions is asymp o ically equal o he numbe o egula bipa i e subdi isions, hence he es ima e ob ained in Subsec ion 4.2 is an uppe bound o he numbe o non-c ossing pa i ions on su aces. All p e ious s eps a e summa ized in Subsec ion 4.5. 4.1. Plana cons uc ions. The dual map o a non-c ossing pa i ion on a disk is a ee, which is called he non-c ossing pa i ion ee associa ed wi h he non-c ossing pa i ion. To abb e ia e his no a ion, we simply say ee associa ed o he co esponding non-c ossing pa i ion. This ee co esponds o he no ion o dual map o su aces wi h bounda y in oduced in Subsec ion 2.2. Recall ha e ices o deg ee one a e called he dangling lea es o he ee. In ees associa ed o non-c ossing pa i ions we ha e h ee ypes o e ices: e ices o he ee a e called block e ices i hey a e associa ed wi h a block o he non-c ossing pa i ion. The emaining e ices a e ei he non-block e ices o danglings. By cons uc ion, all e ices adjacen o a block e ex a e non-block e ices. Con e sely, each e ex adjacen o a non-block e ex is ei he a block e ex o a dangling. G aphically, we use he symbols  o block e ices,  o non-block e ices, and ◦ o danglings. Non-c ossing pa i ions ees a e oo ed: he oo o a non-c ossing pa i ion ee is de ined by he oo o he ini ial non-c ossing pa i ion on a disk (i.e, he oo om e ex 1 o e ex 2). The block e ex which ca ies he ole o he oo e ex o he ee is he one associa ed wi h he block con aining e ex wi h label 2 (o equi alen ly, he end- e ex o he oo ). See Figu e 6 o an example o his cons uc ion. Figu e 6. A non-c ossing pa i ion on a disk and he associa ed ee. Le Tbe he se o non-c ossing pa i ions ees, and le T=T(z, u) = Pn,m≥0 n,mznum be he co esponding gene a ing unc ion, whe e he a iable zma ks danglings and uma ks block e ices. We use an auxilia y amily B, de ined as he se o ees which a e oo ed a a non-block e ex. Le B=B(z, u) = Pn,m≥0bn,mznumbe he associa ed gene a ing unc ion. The nex lemma gi es he exac enume a ion o Tand B. In pa icula , his lemma implies he well-known Ca alan numbe s o non-c ossing pa i ions on a disk. Lemma 4.1.1. The numbe o non-c ossing ees coun ed by he numbe o danglings and block e ices is enume a ed by he gene a ing unc ion (5) T(z, u) = 1−z(1 −u)−p(z(1 −u)−1)2−4zu 2zu . Fu he mo e, B(z, u) = zT(z, u). P oo . We es ablish combina o ial ela ions be ween Band T om which we deduce he esul . Obse e ha he e is no es ic ion on he numbe o e ices inciden wi h a gi en block. Hence he deg ee o e e y block e ex is a bi a y. This condi ion is ansla ed symbolically ia he ela ion T={}×Seq (B). 16 J. RU´ E, I. SAU, AND D. M. THILIKOS Es ima es o |PΣ(n)|a e ob ained in Lemma 4.3.1, ge ing he bound s a ed in Equa ion (6). In Lemma 4.4.3 we p o e ha |RΣ(n) PΣ(n)|=o(|PΣ(n)|), hence he es ima e in Equa ion (11) holds.  5. Bounding c(Σ) in e ms o cubic maps In his sec ion we ob ain uppe bounds o c(Σ) by doing a mo e e ined analysis o e unc ions gs(z) ( ecall he no a ion used in Subsec ion 4.3). This is done in he ollowing p oposi ion. Lemma 5.0.2. The unc ion c(Σ) de ined in Lemma 4.3.1 sa is ies (12) c(Σ) ≤2β(Σ)|CΣ|. P oo . Fo each s∈CΣ, we ob ain bounds o gs(1/4). We use Table 4, which is a simpli ica ion o Table 3. Now we a e only conce ned abou he cons an e m on each GF. Table 4 b ings he ollowing in o ma ion: he main con ibu ion om double ees, ees, and amilies o poin ed ees comes om T−,T, and T•, espec i ely. The cons an s a e 1/4, 2, and 4, espec i ely. Each cubic map has −3χ(Σ) + 2β(Σ) edges (β(Σ) o hem being oo s) and −2χ(Σ) + β(Σ) e ices (β(Σ) o hem being inciden wi h oo s). This cha ac e iza ion p o ides he ollowing uppe bound o gS(1/4): (13) gs(1/4) ≤1 42β(Σ)−3χ(Σ)−β(Σ) 2−3·2χ(Σ)+β(Σ)4β(Σ) = 2β(Σ).  GF Exp ession De elopmen a z= 1/4 T1(z) (1 −4z)−1/2/16 + . . . 1/16(1 −4z)−1/2+. . . T2(z) (1 −4z)−1/2/4 + . . . 1/4(1 −4z)−1/2+. . . T3(z)z2/16(1 −4z)−1/2+. . . 1/256(1 −4z)−1/2+. . . T(z) 1/(2z) + . . . 2 + . . . B(z) 1/2 + . . . 1/2 + . . . T•(z) (1 −4z)−1/2/z +. . . 4(1 −4z)−1/2+. . . B•(z) (1 −4z)−1/2(1 −4z)−1/2 Table 4. A simpli ica ion o Table 3 used in Lemma 4.3.1. The alue o CΣcan be bounded using he esul s in [1, 12]. Indeed, Gao shows in [12] ha he numbe o oo ed cubic maps wi h n e ices in an o ien able su ace o genus1gis asymp o ically equal o g·n5(g−1)/2·(12√3)n, whe e he cons an g ends o ze o as g ends o in ini y [1]. A simila esul is also s a ed in [12] o non-o ien able su aces. By duali y, he numbe o oo ed cubic maps on a su ace Σ o genus g(Σ) wi h β(Σ) aces is asymp o ically equal o g(Σ) ·β(Σ)5(g(Σ)−1)/2·(12√3)β(Σ). To conclude, we obse e ha he elemen s o CΣa e ob ained om oo ed cubic maps wi h β(Σ) aces by adding a oo on each ace di e en om he oo ace. Obse e ha each edge is inciden wi h a mos wo aces, and ha he o al numbe o edges is −3χ(Σ). Consequen ly, he numbe o ways o oo ing a cubic map wi h β(Σ)−1 un oo ed aces is bounded by −6χ(Σ) β(Σ)−1. Lemma 5.0.2, oge he wi h he discussion abo e, yields he ollowing bound o c(Σ). 1 he genus g(Σ) o an o ien able su ace Σ is de ined as g(Σ) = 1 −χ(Σ)/2 (see [15]). ASYMPTOTIC ENUMERATION OF NON-CROSSING PARTITIONS ON SURFACES 17 P oposi ion 5.0.3. The cons an c(Σ) e i ies, o −χ(Σ) → ∞ c(Σ) < 1−χ(Σ)/2·β(Σ)−5χ(Σ)/2·(12√3)β(Σ) ·−6χ(Σ) β(Σ) −1·2β(Σ). Fu he esea ch. In his a icle, we p o ided uppe bounds o |ΠΣ(n)|. This uppe bound is exac o he exponen ial g ow h ( ecall Sec ion 1). Howe e , we canno assu e exac ness o he subexponen ial g ow h. The main p oblem in o de o s a e asymp o ic equali ies is ha |ΠΣ(n)| 6=|PΣ(n)|: he e exis di e en i educible bipa i e subdi isions wi h n e ices which de ine he same non-c ossing pa i ion (see Figu e 10 o an example). Howe e , we conjec u e ha he uppe bound we ha e ob ained is igh . A na u al s a egy o ind lowe bounds wi h he same subexponen ial g ow h could be o conside only a subse o i educible subdi isions gi ing ise o di e en non-c ossing pa i ions. On su aces ob ained om he sphe e his subse migh be de ined as he i educible subdi isions such ha he e a e a leas wo black e ices on each edge o he co esponding scheme (in u- i i ely, such i educible subdi isions do no allow he o a ional symme y a ound a bounda y ha occu s in he example o Figu e 10). Howe e , his condi ion seems no o be su icien on su aces o highe genus. Hence, an open p oblem in his con ex is inding p ecise de ini ions o sub amilies o i educible subdi ision whose enume a ion ma ches ou asymp o ic uppe bound. Figu e 10. Two di e en ep esen a ions o he same pa i ion. Ano he in e es ing p oblem is based on gene alizing he no ion o k- iangula ion o he pa - i ion amewo k and ge ing he asymp o ic enume a ion: he enume a ion o k- iangula ions on a disk was ound using algeb aic me hods in [13]. This no ion can be easily ansla ed o he non-c ossing pa i ion amewo k on a disk, and he exac enume a ion in his case seems o be mo e in ol ed. In he same way as non-c ossing pa i ions on su aces play a c ucial ole o designing algo i hms o g aphs on su aces (see [16]), i u ns ou ha he enume a ion men- ioned abo e is o capi al impo ance in o de o design algo i hm o amilies o g aphs de ined by excluding mino s. Acknowledgemen s. We would like o hank Ma c Noy o poin ing us o e e ences [1, 12], and he anonymous e e ees o sugges ing in e es ing imp o emen s in he p esen a ion o he esul s. Re e ences [1] Bende , E. A., Gao, Z., and Richmond, L. B. The map asymp o ics cons an g.Elec onic Jou nal o Combina o ics 15, 1 (2008), R51, 8pp. 18 J. RU´ E, I. SAU, AND D. M. THILIKOS [2] Be na di, O., and Ru´ e, J. Enume a ing simplicial decomposi ions o su aces wi h bounda ies. Eu opean J. Combin. 33, 3 (2012), 302–325. [3] Chapuy, G. Asymp o ic enume a ion o cons ella ions and ela ed amilies o maps on o ien able su aces. Combina o ics, P obabili y and Compu ing 18, 4 (2009), 477–516. [4] Chapuy, G., Ma cus, M., and Schae e , G. A bijec ion o oo ed maps on o ien able su aces. SIAM Jou nal on Disc e e Ma hema ics 23, 3 (2009), 1587–1611. [5] Co i, R. Indecomposable pe mu a ions, hype maps and labeled dyck pa hs. Jou nal o Combina o ial The- o y, Se ies A 116, 8 (2009), 1326–1343. [6] Do n, F., Fomin, F. V., and Thilikos, D. M. Fas Subexponen ial Algo i hm o Non-local P oblems on G aphs o Bounded Genus. In P oc. o he 10 h Scandina ian Wo kshop on Algo i hm Theo y (SWAT) (2006), ol. 4059 o LNCS, pp. 172–183. [7] Do n, F., Penninkx, E., Bodlaende , H. L., and Fomin, F. V. E icien Exac Algo i hms on Plana G aphs: Exploi ing Sphe e Cu B anch Decomposi ions. In P oc. o he 13 h Annual Eu opean Symposium on Algo i hms (ESA) (2005), ol. 3669 o LNCS, pp. 95–106. [8] Edelman, P. H., and Simion, R. Chains in he la ice o nonc ossing pa i ions. Disc e e Ma hema ics 126, 1-3 (1994), 107–119. [9] Flajole , P., and Noy, M. Analy ic combina o ics o non-c ossing con igu a ions. Disc e e Ma hema ics 204, 1 (1999), 203–229. [10] Flajole , P., and Odlyzko, A. Singula i y analysis o gene a ing unc ions. SIAM Jou nal on Disc e e Ma hema ics 3, 2 (1990), 216–240. [11] Flajole , P., and Sedgewick, R. Analy ic Combina o ics. Camb idge Uni . P ess, 2008. [12] Gao, Z. The numbe o oo ed iangula maps on a su ace. Jou nal o Combina o ial Theo y, Se ies B 52, 2 (1991), 236–249. [13] Jonsson, J. Gene alized iangula ions and diagonal- ee subse s o s ack polyominoes. Jou nal o Combi- na o ial Theo y, Se ies A 112, 1 (2005), 117 – 142. [14] Lando, S. K., and Z onkin, A. K. G aphs on Su aces and Thei Applica ions, ol. 141 o Encyclopaedia o Ma hema ical Sciences: Lowe -Dimensional Topology II. Sp inge -Ve lag, 2004. [15] Moha , B., and Thomassen, C. G aphs on su aces. John Hopkins Uni e si y P ess, 2001. [16] Ru´ e, J., Sau, I., and Thilikos, D. M. Dynamic p og amming o g aphs on su aces. To appea in ACM T ansac ions on Algo i hms. A ailable on-line a h p://a xi .o g/abs/1104.2486. [17] Seymou , P., and Thomas, R. Call ou ing and he a ca che . Combina o ica 14, 2 (1994), 217–241. [18] Simion, R. Combina o ial s a is ics on nonc ossing pa i ions. Jou nal o Combina o ial Theo y, Se ies A 66, 2 (1994), 270–301. [19] S anley, R. P. Enume a i e combina o ics. Vol. 2, ol. 62 o Camb idge S udies in Ad anced Ma hema ics. Camb idge Uni e si y P ess, Camb idge, 1999. J. Ru´ e: CNRS, Labo a oi e d’In o ma ique, ´ Ecole Poly echnique, 91128 Palaiseau Cedex, F ance E-mail add ess:[email p o ec ed] I. Sau: CNRS, LIRMM, Mon pellie , F ance E-mail add ess:[email p o ec ed] D. M. Thilikos: Depa men o Ma hema ics, Na ional and Kapodis ian Uni e si y o A hens, G eece E-mail add ess:[email p o ec ed]