{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T19:16:32Z","timestamp":1774034192168,"version":"3.50.1"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T00:00:00Z","timestamp":1773964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T00:00:00Z","timestamp":1773964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00493-026-00208-z","type":"journal-article","created":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T18:23:33Z","timestamp":1774031013000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Rigidity Matroids and Linear Algebraic Matroids with Applications to Matrix Completion and Tensor Codes"],"prefix":"10.1007","volume":"46","author":[{"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[]},{"given":"Manik","family":"Dhar","sequence":"additional","affiliation":[]},{"given":"Jiyang","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Sivakanth","family":"Gopi","sequence":"additional","affiliation":[]},{"given":"Matt","family":"Larson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,20]]},"reference":[{"key":"208_CR1","doi-asserted-by":"crossref","unstructured":"Athi, H., Chigullapally, R., Krishnan, P., Lalitha, V.: On the structure of higher order MDS codes, 2023 IEEE Int. Symp. Inform. Theory (ISIT), 1009\u20131014, (2023)","DOI":"10.1109\/ISIT54713.2023.10206712"},{"key":"208_CR2","doi-asserted-by":"crossref","unstructured":"Alrabiah, O., Guruswami, V., Li, R.: AG codes have no list-decoding friends: approaching the Singleton bound requires exponential alphabets, 1367\u20131378, (2024)","DOI":"10.1137\/1.9781611977912.55"},{"key":"208_CR3","doi-asserted-by":"crossref","unstructured":"Alrabiah, O., Guruswami, V., Li, R.: Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields,: STOC\u201924\u2013Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 1458\u20131469,(2024)","DOI":"10.1145\/3618260.3649634"},{"key":"208_CR4","doi-asserted-by":"crossref","unstructured":"Anderson, N.: Matroid products in tropical geometry, Res. Math. Sci., 11, no. 2, Paper No. 38, 28, (2024)","DOI":"10.1007\/s40687-024-00452-z"},{"key":"208_CR5","doi-asserted-by":"crossref","unstructured":"Bernstein, D.\u00a0I., Blekherman, G., Lee, K.: Typical ranks in symmetric matrix completion, J. Pure Appl. Algebra, 225, no. 7, Paper No. 106603, 16, (2021)","DOI":"10.1016\/j.jpaa.2020.106603"},{"key":"208_CR6","doi-asserted-by":"crossref","unstructured":"Brakensiek, J., Dhar, M., Gopi, S.: Improved field size bounds for higher order MDS codes, 2023 IEEE Int. Symp. Inform. Theory (ISIT), 1243\u20131248, (2023)","DOI":"10.1109\/ISIT54713.2023.10206952"},{"key":"208_CR7","doi-asserted-by":"crossref","unstructured":"Brakensiek, J., Dhar, M., Gopi, S.: Generalized GM-MDS: polynomial codes are higher order MDS, 728\u2013739, (2024)","DOI":"10.1145\/3618260.3649637"},{"issue":"8","key":"208_CR8","doi-asserted-by":"publisher","first-page":"5935","DOI":"10.1109\/TIT.2025.3577506","volume":"71","author":"J Brakensiek","year":"2025","unstructured":"Brakensiek, J., Dhar, M., Gopi, S., Zhang, Z.: AG codes achieve list-decoding capacity over constant-sized fields. IEEE Trans. Inform. Theory 71(8), 5935\u20135956 (2025)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"208_CR9","doi-asserted-by":"crossref","unstructured":"Brakensiek, J., Eur, C., Larson, M., Li, S.: Kapranov Degrees, Int. Math. Res. Not. IMRN, 20, rnaf306, (2025)","DOI":"10.1093\/imrn\/rnaf306"},{"key":"208_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.laa.2017.07.016","volume":"533","author":"DI Bernstein","year":"2017","unstructured":"Bernstein, D.I.: Completion of tree metrics and rank 2 matrices. Linear Algebra Appl. 533, 1\u201313 (2017)","journal-title":"Linear Algebra Appl."},{"issue":"11","key":"208_CR11","doi-asserted-by":"publisher","first-page":"7125","DOI":"10.1109\/TIT.2022.3187366","volume":"68","author":"J Brakensiek","year":"2022","unstructured":"Brakensiek, J., Gopi, S., Makam, V.: Lower bounds for maximally recoverable tensor codes and higher order MDS codes. IEEE Trans. Inform. Theory 68(11), 7125\u20137140 (2022)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"208_CR12","doi-asserted-by":"crossref","unstructured":"Brakensiek, J., Gopi, S., Makam, V.: Generic Reed-Solomon codes achieve list-decoding capacity, 1488\u20131501, (2023)","DOI":"10.1145\/3564246.3585128"},{"issue":"2","key":"208_CR13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00454-018-9990-3","volume":"61","author":"G Blekherman","year":"2019","unstructured":"Blekherman, G., Sinn, R.: Maximum likelihood threshold and generic completion rank of graphs. Discrete Comput. Geom. 61(2), 303\u2013324 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"208_CR14","unstructured":"Clinch, Katie, Jackson, Bill, Tanigawa, Shin-ichi, Abstract 3-rigidity and bivariate $$C^1_2$$-splines I: Whiteley\u2019s maximality conjecture, Discrete Anal., Paper No. 2, 50, (2022)"},{"key":"208_CR15","unstructured":"Clinch, K., Jackson, B., Tanigawa, S.-i.: Abstract 3-rigidity and bivariate $$C^1_2$$-splines II: Combinatorial characterization, Discrete Anal., Paper No. 3, 32, (2022)"},{"key":"208_CR16","doi-asserted-by":"crossref","unstructured":"Cai, M., Lee, K., Yu, J.: The tropical variety of symmetric rank 2 matrices, Linear Algebra Appl. 720, 50\u201371 (2025)","DOI":"10.1016\/j.laa.2025.04.011"},{"key":"208_CR17","unstructured":"Crespo\u00a0Ruiz, L.: Realizations of multiassociahedra via bipartite rigidity, (2023) arXiv:2303.15776,"},{"key":"208_CR18","doi-asserted-by":"crossref","unstructured":"Ruiz, L.C., Santos, F.: Bar-and-joint rigidity on the moment curve coincides with cofactor rigidity on a conic, Comb. Theory, 3, no. 1, Paper No. 15, 13, (2023)","DOI":"10.5070\/C63160428"},{"issue":"2","key":"208_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/22M1527507","volume":"8","author":"LC Ruiz","year":"2024","unstructured":"Ruiz, L.C., Francisco, M.: Multitriangulations and tropical Pfaffians. SIAM J. Appl. Algebra Geom. 8(2), 302\u2013332 (2024)","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"4","key":"208_CR20","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1007\/s00454-024-00698-y","volume":"73","author":"CL Ruiz","year":"2025","unstructured":"Ruiz, C.L., Santos, F.: Realizations of multiassociahedra via rigidity. Discrete Comput. Geom. 73(4), 973\u20131015 (2025)","journal-title":"Discrete Comput. Geom."},{"key":"208_CR21","doi-asserted-by":"crossref","unstructured":"Draisma, J., Rinc\u00f3n, F.: Tropical ideals do not realise all Bergman fans, Res. Math. Sci., 8, no. 3, Paper No. 44, 11, (2021)","DOI":"10.1007\/s40687-021-00271-6"},{"key":"208_CR22","doi-asserted-by":"crossref","unstructured":"Develin, M., Santos, F., Sturmfels, B.: On the rank of a tropical matrix, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, Cambridge, pp. 213\u2013242, (2005)","DOI":"10.1017\/9781009701259.014"},{"key":"208_CR23","doi-asserted-by":"crossref","unstructured":"Dau, S.H., Song, W., Yuen, C.: On the existence of MDS codes over small fields with constrained generator matrices, 2014 IEEE International Symposium on Information Theory, 1787\u20131791, (2014)","DOI":"10.1109\/ISIT.2014.6875141"},{"key":"208_CR24","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Hu, G., Kopparty, S., Saraf, S., Wang, C., Yekhanin, S.: Maximally recoverable codes for grid-like topologies, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2092\u20132108,(2017)","DOI":"10.1137\/1.9781611974782.136"},{"issue":"3","key":"208_CR25","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/0404032","volume":"4","author":"JE Graver","year":"1991","unstructured":"Graver, J.E.: Rigidity matroids. SIAM J. Discrete Math. 4(3), 355\u2013368 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"208_CR26","doi-asserted-by":"publisher","first-page":"386","DOI":"10.3150\/16-BEJ881","volume":"24","author":"E Gross","year":"2018","unstructured":"Gross, E., Sullivant, S.: The maximum likelihood threshold of a graph. Bernoulli 24(1), 386\u2013407 (2018)","journal-title":"Bernoulli"},{"key":"208_CR27","doi-asserted-by":"crossref","unstructured":"Guo, Z., Zhang, Z.: Randomly punctured Reed-Solomon codes achieve the list decoding capacity over polynomial-size alphabets, 164\u2013176, (2023)","DOI":"10.1109\/FOCS57990.2023.00019"},{"key":"208_CR28","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/BFb0120924","volume":"14","author":"D Hausmann","year":"1981","unstructured":"Hausmann, D., Korte, B.: Algorithmic versus axiomatic definitions of matroids. Math. Programming Stud. 14, 98\u2013111 (1981)","journal-title":"Math. Programming Stud."},{"key":"208_CR29","doi-asserted-by":"crossref","unstructured":"Holzbaur, L., Puchinger, S., Yaakobi, E., Wachter-Zeh, A.: Correctable erasure patterns in product topologies, 2021 IEEE Int. Symp. Inform. Theory (ISIT), 2054\u20132059, (2021)","DOI":"10.1109\/ISIT45174.2021.9518208"},{"key":"208_CR30","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.jctb.2023.10.012","volume":"165","author":"B Jackson","year":"2024","unstructured":"Jackson, B., Tanigawa, S.: Maximal matroids in weak order posets. J. Combin. Theory Ser. B 165, 20\u201346 (2024)","journal-title":"J. Combin. Theory Ser. B"},{"key":"208_CR31","doi-asserted-by":"crossref","unstructured":"Kalai, G.: Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999), pp. 121\u2013163, (2002)","DOI":"10.2969\/aspm\/03310121"},{"issue":"1","key":"208_CR32","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF02582930","volume":"1","author":"G Kalai","year":"1985","unstructured":"Kalai, G.: Hyperconnectivity of graphs. Graphs Combin. 1(1), 65\u201379 (1985)","journal-title":"Graphs Combin."},{"issue":"2","key":"208_CR33","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s10801-021-01013-1","volume":"54","author":"X Kong","year":"2021","unstructured":"Kong, X., Ma, J., Ge, G.: New bounds on the field size for maximally recoverable codes instantiating grid-like topologies. J. Algebraic Combin. 54(2), 529\u2013557 (2021)","journal-title":"J. Algebraic Combin."},{"issue":"8","key":"208_CR34","doi-asserted-by":"publisher","first-page":"5515","DOI":"10.1090\/tran\/6512","volume":"368","author":"G Kalai","year":"2016","unstructured":"Kalai, G., Nevo, E., Novik, I.: Bipartite rigidity. Trans. Amer. Math. Soc. 368(8), 5515\u20135545 (2016)","journal-title":"Trans. Amer. Math. Soc."},{"key":"208_CR35","unstructured":"Kir\u00e1ly, F., Rosen, Z., Theran, L.: Algebraic matroids with graph symmetry (2013). arXiv:1312.3777"},{"key":"208_CR36","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01534980","volume":"4","author":"G Laman","year":"1970","unstructured":"Laman, G.: On graphs and rigidity of plane skeletal structures. J. Engrg. Math. 4, 331\u2013340 (1970)","journal-title":"J. Engrg. Math."},{"key":"208_CR37","doi-asserted-by":"crossref","unstructured":"Lang, S.: Algebra, third, Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, (2002)","DOI":"10.1007\/978-1-4613-0041-0"},{"issue":"4","key":"208_CR38","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1137\/20M1323345","volume":"50","author":"S Lovett","year":"2021","unstructured":"Lovett, S.: Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture. SIAM J. Comput. 50(4), 1248\u20131262 (2021)","journal-title":"SIAM J. Comput."},{"key":"208_CR39","unstructured":"Lov\u00e1sz, L.: Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), pp. 45\u201386, (1977)"},{"issue":"1","key":"208_CR40","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(81)90172-2","volume":"36","author":"ML Vergnas","year":"1981","unstructured":"Vergnas, M.L.: On products of matroids. Discrete Math. 36(1), 49\u201355 (1981)","journal-title":"Discrete Math."},{"key":"208_CR41","doi-asserted-by":"crossref","unstructured":"Liu, H., Wei, H., Wachter-Zeh, A., Schwartz, M.: Linearized Reed\u2013Solomon codes with support-constrained generator matrix, 2023 IEEE Information Theory Workshop (ITW), 7\u201312, (2023)","DOI":"10.1109\/ITW55543.2023.10161635"},{"issue":"1","key":"208_CR42","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0603009","volume":"3","author":"L Lov\u00e1sz","year":"1982","unstructured":"Lov\u00e1sz, L., Yemini, Y.: On generic rigidity in the plane. SIAM J. Algebraic Discrete Methods 3(1), 91\u201398 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"208_CR43","unstructured":"Mason, J.\u00a0H.: Glueing matroids together: a study of Dilworth truncations and matroid analogues of exterior and symmetric powers, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 519\u2013561 (1981)"},{"key":"208_CR44","unstructured":"Matsumura, H.: Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge: Translated from the Japanese by M, Reid (1986)"},{"key":"208_CR45","first-page":"294","volume":"27","author":"JC Maxwell","year":"1864","unstructured":"Maxwell, J.C.: On the calculation of the equilibrium and stiffness of frames: Philos. Mag. 27, 294\u2013299 (1864)","journal-title":"Mag."},{"key":"208_CR46","unstructured":"Muralidhar, S., Lloyd, W., Roy, S., Hill, C., Lin, E., Liu, W., Pan, S., Shankar, S., Sivakumar, V., Tang, L., Kumar, S.: f4: Facebook\u2019s warm BLOB storage system, 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 383\u2013398 (2014)"},{"key":"208_CR47","unstructured":"James, O.: Matroid theory, Second, Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, (2011)"},{"key":"208_CR48","doi-asserted-by":"crossref","unstructured":"Pollaczek-Geiringer, H.: \u00dcber die gliederung ebener fachwerke. Z. Angew. Math. Mech. 7, 58\u201372 (1927)","DOI":"10.1002\/zamm.19270070107"},{"issue":"12","key":"208_CR49","doi-asserted-by":"publisher","first-page":"7798","DOI":"10.1109\/TIT.2022.3194521","volume":"68","author":"RM Roth","year":"2022","unstructured":"Roth, R.M.: Higher-order MDS codes. IEEE Trans. Inform. Theory 68(12), 7798\u20137816 (2022)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"208_CR50","unstructured":"Ron-Zewi, N., Venkitesh, S., Wootters, M.: Efficient list-decoding of polynomial ideal codes with optimal list size, (2024) arXiv:2401.14517"},{"key":"208_CR51","doi-asserted-by":"crossref","unstructured":"Singer, A., Cucuringu, M.: Uniqueness of low-rank matrix completion by rigidity theory, SIAM J. Matrix Anal. Appl., 31,(2009\/10), no. 4, 1621\u20131641","DOI":"10.1137\/090750688"},{"issue":"4","key":"208_CR52","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach. 27(4), 701\u2013717 (1980)","journal-title":"J. Assoc. Comput. Mach."},{"key":"208_CR53","doi-asserted-by":"crossref","unstructured":"Shivakrishna, D., Lalitha, V.: Properties of maximally recoverable product codes and higher order MDS codes, 2022 National Conference on Communications (NCC), 233\u2013238, (2022)","DOI":"10.1109\/NCC55593.2022.9806469"},{"key":"208_CR54","doi-asserted-by":"crossref","unstructured":"Shivakrishna, D., Arvind, R.V., Lalitha, V., Sasidharan, B.: On maximally recoverable codes for product topologies, 2018 Twenty Fourth National Conference on Communications (NCC), 1\u20136, (2018)","DOI":"10.1109\/NCC.2018.8599965"},{"issue":"3","key":"208_CR55","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1137\/20M138795X","volume":"52","author":"C Shangguan","year":"2023","unstructured":"Shangguan, C., Tamo, I.: Generalized singleton bound and list-decoding Reed-Solomon codes beyond the Johnson radius. SIAM J. Comput. 52(3), 684\u2013717 (2023)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"208_CR56","first-page":"731","volume":"377","author":"M Tsakiris","year":"2024","unstructured":"Tsakiris, M.: Results on the algebraic matroid of the determinantal variety: Trans. Amer. Math. Soc. 377(1), 731\u2013751 (2024)","journal-title":"Amer. Math. Soc."},{"issue":"1","key":"208_CR57","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02187716","volume":"4","author":"W Whiteley","year":"1989","unstructured":"Whiteley, W.: A matroid on hypergraphs, with applications in scene analysis and geometry. Discrete Comput. Geom. 4(1), 75\u201395 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"208_CR58","doi-asserted-by":"crossref","unstructured":"Whiteley, W.: Some matroids from discrete applied geometry, Matroid theory (Seattle, WA, 1995), pp. 171\u2013311, (1996)","DOI":"10.1090\/conm\/197\/02540"},{"issue":"12","key":"208_CR59","doi-asserted-by":"publisher","first-page":"7868","DOI":"10.1109\/TIT.2019.2932663","volume":"65","author":"H Yildiz","year":"2019","unstructured":"Yildiz, H., Hassibi, B.: Optimum linear codes with support-constrained generator matrices over small fields. IEEE Trans. Inform. Theory 65(12), 7868\u20137875 (2019)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"208_CR60","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM \u201979, Internat. Sympos., Marseille, 1979), pp. 216\u2013226, (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-026-00208-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-026-00208-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-026-00208-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T18:23:36Z","timestamp":1774031016000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-026-00208-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,20]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["208"],"URL":"https:\/\/doi.org\/10.1007\/s00493-026-00208-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,20]]},"assertion":[{"value":"14 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"15"}}