Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 4
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Shifted witten classes and topological recursion

  • Charbonnier, Séverin
  • Chidambaram, Nitin Kumar
  • García Failde, Elba|||0000-0001-7901-5819
  • Giacchetto, Alessandro
First published in [Transactions of the American Mathematical Society] in [Volume 377, Number 2], published by the American Mathematical Society., The Witten r-spin class defines a non-semisimple cohomological field theory. Pandharipande, Pixton and Zvonkine studied two special shifts of the Witten class along two semisimple directions of the associated Dubrovin–Frobenius manifold using the Givental–Teleman reconstruction theorem. We show that the -matrix and the translation of these two specific shifts can be constructed from the solutions of two differential equations that generalise the classical Airy differential equation. Using this, we prove that the descendant intersection theory of the shifted Witten classes satisfies topological recursion on two -parameter families of spectral curves. By taking the limit as the parameter goes to zero, we prove that the descendant intersection theory of the Witten -spin class can be computed by topological recursion on the -Airy spectral curve. We finally show that this proof suffices to deduce Witten’s -spin conjecture, already proved by Faber, Shadrin and Zvonkine, which claims that the generating series of -spin intersection numbers is the tau function of the -KdV hierarchy that satisfies the string equation., Acknowledgments: Wet hank Alessandro Chiodo, Sergey Shadrin, Di Yangand Dimitri Zvonkine for useful discussions. We are grateful to the referees for their helpful comments and corrections. N.K.C. thanks the Max Planck Institute for Mathematics for the excellent working conditions provided. We thank the Institut de Mathématiques de Jussieu - Paris Rive Gauche for its hospitality. Funding: The first author was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. ERC-2016-STG 716083 “CombiTop”). The third author was supported by the same grant when this work started. This work was partly a result of the ERC-SyG project, Recursive and Exact New Quantum Theory (ReNewQuantum) which received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 810573. The fourth author had been supported by the Institut de Physique Théorique Paris (IPhT), CEA, Université de Saclay., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Short synchronizing words for random automata

  • Chapuy, Guillaume
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ¿ of such length, and a state v0, such that ¿ sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykula [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ¿ we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p. Our proof introduces the concept of ¿-trees, for a word ¿, that is, automata in which the ¿-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ¿-tree for some word ¿ of length at most (1 + e) log2(n), for any e > 0. The existence of the (random) word ¿ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Short synchronizing words for random automata

  • Chapuy, Guillaume
  • Perarnau Llobet, Guillem
We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ¿ of such length, and a state v0, such that ¿ sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykula [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ¿ we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p. Our proof introduces the concept of ¿-trees, for a word ¿, that is, automata in which the ¿-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ¿-tree for some word ¿ of length at most (1 + e) log2(n), for any e > 0. The existence of the (random) word ¿ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Shifted witten classes and topological recursion

  • Charbonnier, Séverin
  • Chidambaram, Nitin Kumar
  • García Failde, Elba
  • Giacchetto, Alessandro
First published in [Transactions of the American Mathematical Society] in [Volume 377, Number 2], published by the American Mathematical Society., The Witten r-spin class defines a non-semisimple cohomological field theory. Pandharipande, Pixton and Zvonkine studied two special shifts of the Witten class along two semisimple directions of the associated Dubrovin–Frobenius manifold using the Givental–Teleman reconstruction theorem. We show that the -matrix and the translation of these two specific shifts can be constructed from the solutions of two differential equations that generalise the classical Airy differential equation. Using this, we prove that the descendant intersection theory of the shifted Witten classes satisfies topological recursion on two -parameter families of spectral curves. By taking the limit as the parameter goes to zero, we prove that the descendant intersection theory of the Witten -spin class can be computed by topological recursion on the -Airy spectral curve. We finally show that this proof suffices to deduce Witten’s -spin conjecture, already proved by Faber, Shadrin and Zvonkine, which claims that the generating series of -spin intersection numbers is the tau function of the -KdV hierarchy that satisfies the string equation., Acknowledgments: Wet hank Alessandro Chiodo, Sergey Shadrin, Di Yangand Dimitri Zvonkine for useful discussions. We are grateful to the referees for their helpful comments and corrections. N.K.C. thanks the Max Planck Institute for Mathematics for the excellent working conditions provided. We thank the Institut de Mathématiques de Jussieu - Paris Rive Gauche for its hospitality. Funding: The first author was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. ERC-2016-STG 716083 “CombiTop”). The third author was supported by the same grant when this work started. This work was partly a result of the ERC-SyG project, Recursive and Exact New Quantum Theory (ReNewQuantum) which received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 810573. The fourth author had been supported by the Institut de Physique Théorique Paris (IPhT), CEA, Université de Saclay., Peer Reviewed, Postprint (author's final draft)