Pasar al contenido principal

COMBINATORIA CONTEMPORANEA Y SUS APLICACIONES

PID2023-147202NB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2023
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

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

Error-correcting codes and absolutely maximally entangled states for mixed-dimensional Hilbert spaces

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Zhang, Raven
© 2026 American Physical Society. Simeon Ball and Raven Zhang, "Error-correcting codes and absolutely maximally entangled states for mixed dimensional Hilbert spaces", Phys. Rev. A 113, 012432 (2026). Available at: https://doi.org/10.1103/yqck-92fb, A major difficulty in quantum computation is the ability to implement fault-tolerant computations, protecting information against undesired interactions with the environment. Stabilizer codes were introduced as a means to protect information when storing or applying computations in Hilbert spaces where the local dimension is fixed, i.e., in Hilbert spaces of the form (ℂ𝐷)⊗𝑛. If 𝐷 is a prime power then one can consider stabiliser codes over finite fields [A. Ketkar et al., IEEE Trans. Inf. Theory 52, 4892 (2006)], which allows a deeper mathematical structure to be used to develop stabilizer codes. However, there is no practical reason that the subsystems should have the same local dimension and in this article we introduce a stabilizer formalism for mixed-dimensional Hilbert spaces, i.e., of the form ℂ𝐷1⊗⋯⊗ℂ𝐷𝑛. More generally, we define and prove a Singleton bound for quantum error-correcting codes of mixed-dimensional Hilbert spaces. We redefine entanglement measures for these Hilbert spaces and follow [F. Huber et al., J. Phys. A: Math. Theor. 51, 175301 (2018)] and define absolutely maximally entangled states as states which maximize this entanglement measure. We provide examples of absolutely maximally entangled states in spaces of dimensions not previously known to have absolutely maximally entangled states., This research is supported by the Spanish Ministry of Science, Innovation and Universities grant PID2023-147202NB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Griesmer type bounds for additive codes over finite fields, integral and fractional MDS codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Lavrauw, Michel
  • Popatia, Tabriz Arun Avery|||0009-0003-0220-4277
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10623-024-01519-2, In this article we prove Griesmer type bounds for additive codes over finite fields. These new bounds give upper bounds on the length of maximum distance separable (MDS) codes, codes which attain the Singleton bound. We will also consider codes to be MDS if they attain the fractional Singleton bound, due to Huffman. We prove that this bound in the fractional case can be obtained by codes whose length surpasses the length of the longest known codes in the integral case. For small parameters, we provide exhaustive computational results for additive MDS codes, by classifying the corresponding (fractional) subspace-arcs. This includes a complete classification of fractional additive MDS codes of size 243 over the field of order 9., The first and third author are supported by the Spanish Ministry of Science, Innovation and Universities grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033 and grant PID2023-147202NB-I00
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A construction that preserves the configuration of a matroid, with applications to lattice path matroid

  • Bonin, Joseph E.
  • Mier Vinué, Anna de|||0000-0002-2817-7807
The configuration of a matroid M is the abstract lattice of cyclic flats (flats that are unions of circuits) where we record the size and rank of each cyclic flat, but not the set. One can compute the Tutte polynomial of M , and stronger invariants (notably, the G -invariant), from the configuration. Given a matroid M in which certain pairs of cyclic flats are non-modular, we show how to produce a matroid that is not isomorphic to M but has the same configuration as M . We show that this construction applies to a lattice path matroid if and only if it is not a fundamental transversal matroid, and we enumerate the connected lattice path matroids on [ n ] that are fundamental; these results imply that, asymptotically, almost no lattice path matroids are Tutte unique. We give a sufficient condition for a matroid to be determined, up to isomorphism, by its configuration. We treat constructions that yield matroids with different configurations where each matroid is determined by its configuration and all have the same G -invariant. We also show that for any lattice L other than a chain, there are non-isomorphic transversal matroids that have the same configuration and where the lattices of cyclic flats are isomorphic to L ., We thank the referee for useful, constructive comments. The second author was supportedby the Grant PID2023-147202NB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Geometrical constructions of purity testing protocols and their applications to quantum communication

  • Trényi, Róbert|||0000-0002-2839-0472
  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Glynn, David G.
  • Curty, Marcos
Purity testing protocols (PTPs), also known as Bell state testing protocols, i.e., protocols that decide with high probability whether or not a distributed bipartite quantum state is a tensor product of Bell states, have been proven to be a useful tool in many quantum communication applications. In this paper, we provide geometrical constructions for such protocols that originate directly from classical linear error correcting codes (LECCs), in a way that the properties of the resulting PTP are completely determined from those of the LECC used in the construction. We investigate the implications of our results in various quantum communication tasks, including error detection, entanglement purification for general quantum error models and quantum message authentication., The work of Róbert Trényi was supported in part by European Union (EU) [QuantERA Accessible Quantifiers of Multipartite Entanglement in Atomic Systems (MENTA)]; in part by the Spanish Ministerio de Ciencia, Innovación y Universidades (MCIU) under Grant PCI2022-132947; in part by Basque Government under Grant IT1470-22; in part by Ministerio de Ciencia e Innovación (MCIN)/Agencia Estatal de Investigación (AEI)/10.13039/501100011033 and “European Regional Development Fund (ERDF) A way of making Europe” under Grant PID2021-126273NB-I00; in part by the “Frontline” Research Excellence Program of the National Research, Development and Innovation Office of Hungary (NKFIH) under Grant KKP133827; and in part by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, through the TKP2021-NVA Funding Scheme, under Grant TKP2021-NVA-04. The work of Simeon Ball was supported by Spanish Ministry of Science, Innovation and Universities under Grant PID2023-147202NB-I00. The work of Marcos Curty was supported in part by Galician Regional Government (consolidation of research units: atlanTTic), in part by Spanish Ministry of Economy and Competitiveness (MINECO), in part by the Fondo Europeo de Desarrollo Regional (FEDER) under Grant PID2020-118178RBC21 and Grant PID2024-162270OB-I00, in part by the Spanish Ministry of Science and Innovation (MICIN) with funding from European Union NextGenerationEU under Grant PRTRC17.I1, in part by Galician Regional Government with own funding through the “Planes Complementarios de I+D+I con las Comunidades Autónomas” in Quantum Communication, in part by the “Hub Nacional de Excelencia en Comunicaciones Cuánticas” funded by Spanish Ministry for Digital Transformation and the Public Service and European Union NextGenerationEU, in part by European Union’s Horizon Europe Framework Program through the Marie Sklodowska-Curie Grant 101072637 (Project QSI), in part by the project “Quantum Secure Networks Partnership” (QSNP) under Grant 101114043, in part by European Union via European Health and Digital Executive Agency (HADEA) through the Project QuTechSpace under Grant 101135225 and through the Project IberianQCI under Grant 101249593, and in part by the Programa de Cooperación Interreg VI-A Spain–Portugal (POCTEP) 2021–2027 through the Project QUANTUM IBER IA entitled by “Impulso estratégico de las capacidades en tecnologías cuánticas e inteligencia artificial en el espacio ibérico transfronterizo"., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Clique density vs blowups

  • Bradac, Domagoj
  • Liu, Hong
  • Wu, Zhuo|||0009-0008-5144-7335
  • Xu, Zixiang
A well-known theorem of Nikiforov asserts that any graph with a positive ¿¿-density contains a logarithmic blowup of ¿¿. In this paper, we explore variants of Nikiforov’s result in the following form. Given ¿,¿ ¿N, when a positive ¿¿-density implies the existence of a significantly larger (with almost linear size) blowup of ¿¿? Our results include: For an ¿-vertex ordered graph ¿ with no induced monotone path ¿6, if its complement ¿ has positive triangle density, then ¿ contains a biclique of size O¿(¿log¿¿). This strengthens a recent result of Pach and Tomon. For general ¿, let ¿¿(¿) be the minimum ¿ ¿N such that for any ¿-vertex ordered graph ¿ with no induced monotone ¿2¿¿, if ¿ has positive ¿¿-density, then ¿ contains a biclique of size O¿( ¿log¿¿). Using concentration of measure and the isodiametric inequality on high dimensional spheres, we provide constructions showing that, surprisingly, ¿¿(¿) grows quadratically. On the other hand, we relate the problem of upper bounding ¿¿(¿) to a certain Ramsey problem and determine ¿¿(¿) up to a factor of 2. Any incomparability graph with positive ¿¿-density contains a blowup of ¿¿ of size O¿( ¿ log¿¿ ). This confirms a conjecture of Tomon in a stronger form. In doing so, we obtain a strong regularity type lemma for incomparability graphs with no large blowups of a clique, which is of independent interest. We also prove that any ¿-comparability graph with positive ¿(2¿h-2)¿+1-density contains a blowup of ¿h of size O¿(¿), where the constant (2¿h-2)¿ +1 is optimal. The ¿ log¿¿ size of the blowups in all our results are optimal up to a constant factor., Hong Liu, Zixiang Xu: supported by IBS-R029-C4. Zhuo Wu: Z. Wu acknowledge the bilateral AEI+DFG research project PCI2024-155080-2: SRC-ExCo-Structure, Randomness and Computational Methods in Extremal Combinatorics, and the PID2023-147202NB-I00. COCOA: COntemporary COmbinatorics and its Applications, all of them funded by MICIU/AEI/10.13039/501100011033.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the number of monochromatic solutions to multiplicative equations

  • Aragão, Lucas
  • Chapman, Jonathan
  • Ortega Sánchez Colomer, Miquel|||0009-0003-4043-7266
  • Gomes Lauriano de Souza, Victor
The following question was asked by Prendiville: given an r-colouring of the interval {2,...,N}, what is the minimum number of monochromatic solutions of the equation xy = z? For r = 2, we show that there are always asymptotically at least (1/2sqrt(2))N^(1/2)*log(N) monochromatic solutions, and that the leading constant is sharp. For r = 3 and r = 4 we obtain tight results up to a multiplicative logarithmic factor. We also provide bounds for more colours and other multiplicative equations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Blowing up Dirac's theorem

  • Lang, Richard Johannes|||0000-0002-7661-934X
  • Sanhueza Matamala, Nicolás
We show that every graph G on n vertices with d(G) >= (1/2 + e)N is spanned by a complete blow-up of a cycle with clusters of nearly uniform size O(log n). The proof is based on a recently introduced approach for finding vertex-spanning substructures via blow-up covers., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Counting cliques without generalized theta graphs

  • Gao, Jun
  • Wu, Zhuo|||0009-0008-5144-7335
  • Xue, Yisai|||0009-0008-6407-1031
The generalized Turán number ex(n,T,F) is the maximum possible number of copies of T in an F-free graph on n vertices for any two graphs T and F. For the book graph Bb, there is a close connection between ex(n,K3,Bt) and the Ruzsa-Szemerédi triangle removal lemma. Motivated by this, in this paper, we study the generalized Turán problem for generalized theta graphs, a natural extension of book graphs. Our main result provides a complete characterization of the magnitude of ex(n,K3,H) when H is a generalized theta graph, indicating when it is quadratic, when it is nearly quadratic, and when it is subquadratic. Furthermore, as an application, we obtain the exact value of ex(n,Kr,kF), where F is an edge-critical generalized theta graph, and 3 <= r <= k+1, extending several recent results., Z. Wu acknowledges the bilateral AEI+DFG research project PCI2024-155080-2: SRC-ExCo– Structure, Randomness and Computational Methods in Extremal Combinatorics, and the PID2023-147202NB-I00 (COCOA: COntemporary COmbinatorics and its Applications), all funded by MICIU/AEI/10.13039/501100011033.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Additive codes from linear codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Popatia, Tabriz Arun Avery|||0009-0003-0220-4277
© 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We introduce two constructions of additive codes over finite fields. Both constructions start with a linear code over a field with q elements and give additive codes over the field with q elements whose minimum distance is demonstrably good., Spanish Ministry of Science, Innovation and Universities (Grant Number: PID2023-147202NB-I00), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The lonely runner conjecture turns 60

  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
  • Serra Albó, Oriol|||0000-0001-8561-4631
The Lonely Runner Conjecture originated in Diophantine approximation is turning 60. Even if the conjecture is still widely open, the flow of partial results, innovative tools and connections to different problems and applications has been steady on its long life. This survey attempts to give a panoramic view of the status of the problem, trying to highlight the contributions of the many papers that it has originated., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Minimum stationary values of sparse random directed graphs

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution (uniqueness regime). We show that the minimum positive stationary value is whp n-(1+C+o(1)) for some constant C=0 determined by the degree distribution, answering a question raised by Bordenave, Caputo and Salez (Probab. Theory Related Fields 170 (2018) 933–960). In particular, C is the competing combination of two factors: (1) the contribution of atypically “thin” in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. Additionally, we give estimates for the expected lower tail of the empirical stationary distribution. As a by-product of our proof, we obtain that the hitting and the cover time are both n1+C+o(1) whp. Our results are in sharp contrast to those of Caputo and Quattropani (Probab. Theory Related Fields 178 (2020) 1011–1066) who showed that under the additional condition of minimum in-degree at least 2 (ergodicity regime), stationary values only have logarithmic fluctuations around n-1., We would like to thanks Pietro Caputo and Matteo Quattropani for insightful discussions on the topic. We are also grateful to the three anonymous reviewers, whose insightful comments have greatly contributed to improving this paper. G.P. was supported by the grants PID2020-113082GB-I00, PID2023-147202NB-I00, PCI2024-155080-2 and the Programme Severo Ochoa y María de Maeztu por Centros y Unidades de Excelencia en I&D (CEX2020-001084-M), all of them funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Geometrical constructions of purity testing protocols and their applications to quantum communication

  • Trényi, Róbert
  • Ball, Simeon Michael
  • Glynn, David G.
  • Curty, Marcos
Purity testing protocols (PTPs), also known as Bell state testing protocols, i.e., protocols that decide with high probability whether or not a distributed bipartite quantum state is a tensor product of Bell states, have been proven to be a useful tool in many quantum communication applications. In this paper, we provide geometrical constructions for such protocols that originate directly from classical linear error correcting codes (LECCs), in a way that the properties of the resulting PTP are completely determined from those of the LECC used in the construction. We investigate the implications of our results in various quantum communication tasks, including error detection, entanglement purification for general quantum error models and quantum message authentication., The work of Róbert Trényi was supported in part by European Union (EU) [QuantERA Accessible Quantifiers of Multipartite Entanglement in Atomic Systems (MENTA)]; in part by the Spanish Ministerio de Ciencia, Innovación y Universidades (MCIU) under Grant PCI2022-132947; in part by Basque Government under Grant IT1470-22; in part by Ministerio de Ciencia e Innovación (MCIN)/Agencia Estatal de Investigación (AEI)/10.13039/501100011033 and “European Regional Development Fund (ERDF) A way of making Europe” under Grant PID2021-126273NB-I00; in part by the “Frontline” Research Excellence Program of the National Research, Development and Innovation Office of Hungary (NKFIH) under Grant KKP133827; and in part by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, through the TKP2021-NVA Funding Scheme, under Grant TKP2021-NVA-04. The work of Simeon Ball was supported by Spanish Ministry of Science, Innovation and Universities under Grant PID2023-147202NB-I00. The work of Marcos Curty was supported in part by Galician Regional Government (consolidation of research units: atlanTTic), in part by Spanish Ministry of Economy and Competitiveness (MINECO), in part by the Fondo Europeo de Desarrollo Regional (FEDER) under Grant PID2020-118178RBC21 and Grant PID2024-162270OB-I00, in part by the Spanish Ministry of Science and Innovation (MICIN) with funding from European Union NextGenerationEU under Grant PRTRC17.I1, in part by Galician Regional Government with own funding through the “Planes Complementarios de I+D+I con las Comunidades Autónomas” in Quantum Communication, in part by the “Hub Nacional de Excelencia en Comunicaciones Cuánticas” funded by Spanish Ministry for Digital Transformation and the Public Service and European Union NextGenerationEU, in part by European Union’s Horizon Europe Framework Program through the Marie Sklodowska-Curie Grant 101072637 (Project QSI), in part by the project “Quantum Secure Networks Partnership” (QSNP) under Grant 101114043, in part by European Union via European Health and Digital Executive Agency (HADEA) through the Project QuTechSpace under Grant 101135225 and through the Project IberianQCI under Grant 101249593, and in part by the Programa de Cooperación Interreg VI-A Spain–Portugal (POCTEP) 2021–2027 through the Project QUANTUM IBER IA entitled by “Impulso estratégico de las capacidades en tecnologías cuánticas e inteligencia artificial en el espacio ibérico transfronterizo"., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Additive codes from linear codes

  • Ball, Simeon Michael
  • Popatia, Tabriz Arun Avery
© 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We introduce two constructions of additive codes over finite fields. Both constructions start with a linear code over a field with q elements and give additive codes over the field with q elements whose minimum distance is demonstrably good., Spanish Ministry of Science, Innovation and Universities (Grant Number: PID2023-147202NB-I00), Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the number of monochromatic solutions to multiplicative equations

  • Aragão, Lucas
  • Chapman, Jonathan
  • Ortega Sánchez Colomer, Miquel
  • Gomes Lauriano de Souza, Victor
The following question was asked by Prendiville: given an r-colouring of the interval {2,...,N}, what is the minimum number of monochromatic solutions of the equation xy = z? For r = 2, we show that there are always asymptotically at least (1/2sqrt(2))N^(1/2)*log(N) monochromatic solutions, and that the leading constant is sharp. For r = 3 and r = 4 we obtain tight results up to a multiplicative logarithmic factor. We also provide bounds for more colours and other multiplicative equations., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The lonely runner conjecture turns 60

  • Perarnau Llobet, Guillem
  • Serra Albó, Oriol
The Lonely Runner Conjecture originated in Diophantine approximation is turning 60. Even if the conjecture is still widely open, the flow of partial results, innovative tools and connections to different problems and applications has been steady on its long life. This survey attempts to give a panoramic view of the status of the problem, trying to highlight the contributions of the many papers that it has originated., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Griesmer type bounds for additive codes over finite fields, integral and fractional MDS codes

  • Ball, Simeon Michael
  • Lavrauw, Michel
  • Popatia, Tabriz Arun Avery
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10623-024-01519-2, In this article we prove Griesmer type bounds for additive codes over finite fields. These new bounds give upper bounds on the length of maximum distance separable (MDS) codes, codes which attain the Singleton bound. We will also consider codes to be MDS if they attain the fractional Singleton bound, due to Huffman. We prove that this bound in the fractional case can be obtained by codes whose length surpasses the length of the longest known codes in the integral case. For small parameters, we provide exhaustive computational results for additive MDS codes, by classifying the corresponding (fractional) subspace-arcs. This includes a complete classification of fractional additive MDS codes of size 243 over the field of order 9., The first and third author are supported by the Spanish Ministry of Science, Innovation and Universities grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033 and grant PID2023-147202NB-I00, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Blowing up Dirac's theorem

  • Lang, Richard Johannes
  • Sanhueza Matamala, Nicolás
We show that every graph G on n vertices with d(G) >= (1/2 + e)N is spanned by a complete blow-up of a cycle with clusters of nearly uniform size O(log n). The proof is based on a recently introduced approach for finding vertex-spanning substructures via blow-up covers., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Minimum stationary values of sparse random directed graphs

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution (uniqueness regime). We show that the minimum positive stationary value is whp n-(1+C+o(1)) for some constant C=0 determined by the degree distribution, answering a question raised by Bordenave, Caputo and Salez (Probab. Theory Related Fields 170 (2018) 933–960). In particular, C is the competing combination of two factors: (1) the contribution of atypically “thin” in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. Additionally, we give estimates for the expected lower tail of the empirical stationary distribution. As a by-product of our proof, we obtain that the hitting and the cover time are both n1+C+o(1) whp. Our results are in sharp contrast to those of Caputo and Quattropani (Probab. Theory Related Fields 178 (2020) 1011–1066) who showed that under the additional condition of minimum in-degree at least 2 (ergodicity regime), stationary values only have logarithmic fluctuations around n-1., We would like to thanks Pietro Caputo and Matteo Quattropani for insightful discussions on the topic. We are also grateful to the three anonymous reviewers, whose insightful comments have greatly contributed to improving this paper. G.P. was supported by the grants PID2020-113082GB-I00, PID2023-147202NB-I00, PCI2024-155080-2 and the Programme Severo Ochoa y María de Maeztu por Centros y Unidades de Excelencia en I&D (CEX2020-001084-M), all of them funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A construction that preserves the configuration of a matroid, with applications to lattice path matroid

  • Bonin, Joseph E.
  • Mier Vinué, Anna de
The configuration of a matroid M is the abstract lattice of cyclic flats (flats that are unions of circuits) where we record the size and rank of each cyclic flat, but not the set. One can compute the Tutte polynomial of M , and stronger invariants (notably, the G -invariant), from the configuration. Given a matroid M in which certain pairs of cyclic flats are non-modular, we show how to produce a matroid that is not isomorphic to M but has the same configuration as M . We show that this construction applies to a lattice path matroid if and only if it is not a fundamental transversal matroid, and we enumerate the connected lattice path matroids on [ n ] that are fundamental; these results imply that, asymptotically, almost no lattice path matroids are Tutte unique. We give a sufficient condition for a matroid to be determined, up to isomorphism, by its configuration. We treat constructions that yield matroids with different configurations where each matroid is determined by its configuration and all have the same G -invariant. We also show that for any lattice L other than a chain, there are non-isomorphic transversal matroids that have the same configuration and where the lattices of cyclic flats are isomorphic to L ., We thank the referee for useful, constructive comments. The second author was supportedby the Grant PID2023-147202NB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Error-correcting codes and absolutely maximally entangled states for mixed-dimensional Hilbert spaces

  • Ball, Simeon Michael
  • Zhang, Raven
© 2026 American Physical Society. Simeon Ball and Raven Zhang, "Error-correcting codes and absolutely maximally entangled states for mixed dimensional Hilbert spaces", Phys. Rev. A 113, 012432 (2026). Available at: https://doi.org/10.1103/yqck-92fb, A major difficulty in quantum computation is the ability to implement fault-tolerant computations, protecting information against undesired interactions with the environment. Stabilizer codes were introduced as a means to protect information when storing or applying computations in Hilbert spaces where the local dimension is fixed, i.e., in Hilbert spaces of the form (ℂ𝐷)⊗𝑛. If 𝐷 is a prime power then one can consider stabiliser codes over finite fields [A. Ketkar et al., IEEE Trans. Inf. Theory 52, 4892 (2006)], which allows a deeper mathematical structure to be used to develop stabilizer codes. However, there is no practical reason that the subsystems should have the same local dimension and in this article we introduce a stabilizer formalism for mixed-dimensional Hilbert spaces, i.e., of the form ℂ𝐷1⊗⋯⊗ℂ𝐷𝑛. More generally, we define and prove a Singleton bound for quantum error-correcting codes of mixed-dimensional Hilbert spaces. We redefine entanglement measures for these Hilbert spaces and follow [F. Huber et al., J. Phys. A: Math. Theor. 51, 175301 (2018)] and define absolutely maximally entangled states as states which maximize this entanglement measure. We provide examples of absolutely maximally entangled states in spaces of dimensions not previously known to have absolutely maximally entangled states., This research is supported by the Spanish Ministry of Science, Innovation and Universities grant PID2023-147202NB-I00., Peer Reviewed, Postprint (author's final draft)