{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:12Z","timestamp":1787323512890,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We show that for any regular matroid on m elements and $\\alpha \\geq 1$, the number of $\\alpha$-minimum circuits, or circuits whose size is at most an $\\alpha$-multiple of the minimum size of a circuit in the matroid, is bounded by $m^{O(\\alpha^2)}.$ This generalizes a result of Karger for the number of $\\alpha$-minimum cuts in a graph. As a consequence, we obtain similar bounds on the number of $\\alpha$-shortest vectors in totally unimodular lattices and on the number of $\\alpha$-minimum weight code words in regular codes.<\/jats:p>","DOI":"10.1137\/20m1338642","type":"journal-article","created":{"date-parts":[[2021,7,27]],"date-time":"2021-07-27T11:11:40Z","timestamp":1627384300000},"page":"1688-1705","source":"Crossref","is-referenced-by-count":0,"title":["On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8623-0872","authenticated-orcid":true,"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0255-1119","authenticated-orcid":true,"given":"Nisheeth K.","family":"Vishnoi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,7,27]]},"reference":[{"key":"atypb1","first-page":"10","author":"Ajtai M.","year":"1998","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00071-X"},{"key":"atypb3","unstructured":"M. Aprile and S. Fiorini,\n                      Regular Matroids Have Polynomial Extension Complexity\n                      , preprint, arXiv:1909.08539, 2019,https:\/\/arxiv.org\/abs\/1909.08539."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2001.3206"},{"key":"atypb5","unstructured":"A. Barg,\n                      Error-Correcting Codes\n                      , Lecture notes, University of Maryland,http:\/\/www.ece.umd.edu\/~abarg\/626-2009\/notes2005\/lecture25.pdf, 2005."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.02.008"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J. H. Conway, N. J. A. Sloane, and E. Bannai,\n                      Sphere-Packings, Lattices, and Groups\n                      , Springer-Verlag, Berlin, 1987.","DOI":"10.1007\/978-1-4757-2016-7"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Dinitz and G. Kortsarz,\n                      Matroid secretary for regular and decomposable matroids\n                      , in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, SIAM, Philadelphia, pp. 108-118, 2013,http:\/\/dl.acm.org\/citation.cfm?id=2627817.2627825.","DOI":"10.1137\/1.9781611973105.8"},{"key":"atypb9","first-page":"1","author":"Fomin F. V.","year":"2017","journal-title":"Poland"},{"key":"atypb10","first-page":"1433","author":"Fomin F. V.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"T. Gaven\u010diak, D. Kr\u00e1l, and S.I. Oum,\n                      Deciding first order properties of matroids\n                      , in Automata, Languages, and Programming, 2012, Springer-Verlag, Berlin, pp. 239-250.","DOI":"10.1007\/978-3-642-31585-5_24"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-015-0251-3"},{"key":"atypb13","first-page":"521","author":"Goldberg L. A.","year":"2011","journal-title":"Berlin"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"A. Golynski and J. D. Horton,\n                      A polynomial time algorithm to find the minimum cycle basis of a regular matroid\n                      , in Algorithm Theory-SWAT 2002, M. Penttonen and E. M. Schmidt, eds., 2002, Springer-Verlag, Berlin, pp. 200-209.","DOI":"10.1007\/3-540-45471-3_21"},{"key":"atypb15","first-page":"10","volume":"74","author":"Gurjar R.","year":"2018","journal-title":"Czech Republic"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"R. Gurjar and N. K. Vishnoi,\n                      On the number of circuits in regular matroids (with connections to lattices and codes)\n                      , in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, CA, 2019, pp. 861-880,https:\/\/doi.org\/10.1137\/1.9781611975482.53.","DOI":"10.1137\/1.9781611975482.53"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/18.412711"},{"key":"atypb18","unstructured":"R. Kapadia,\n                      Finding Shortest Circuits in Binary Matroids\n                      , The Matroid Union (blog),http:\/\/matroidunion.org\/?p=1106, 2014."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298340"},{"key":"atypb20","first-page":"21","author":"Karger D. R.","year":"1993","journal-title":"Philadelphia"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.924700"},{"key":"atypb22","unstructured":"N. Kashyap,\n                      Regular Codes Are Not Asymptotically Good\n                      ,https:\/\/ece.iisc.ac.in\/~nkashyap\/Papers\/regular_codes.pdf, 2009."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2002.0606"},{"key":"atypb24","unstructured":"N. Linial and J. Mosheiff,\n                      On the Weight Distribution of Random Binary Linear Codes\n                      , CoRR, abs\/1806.08392,https:\/\/arxiv.org\/abs\/1806.08392, 2018."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"S. Onn,\n                      Nonlinear Discrete Optimization: An Algorithmic Theory\n                      , Zurich Lectures in Advanced Mathematics, European Mathematical Society Publishing House, Z\u00fcrich, Switzerland, 2010,https:\/\/books.google.co.il\/books?id=wzAGMQAACAAJ.","DOI":"10.4171\/093"},{"key":"atypb26","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford Grad. Texts Math., Oxford University Press, New York, 2006."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00202-A"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/346048.346049"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190160103"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90030-4"},{"key":"atypb32","unstructured":"K. Truemper,\n                      Matroid Decomposition\n                      , Leibniz, Plano, TX, 1998."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.2140\/moscow.2019.8.163"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0197704"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2012.07.005"},{"key":"atypb36","first-page":"635","author":"Yamane T.","year":"2018","journal-title":"Switzerland"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1338642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:06:47Z","timestamp":1787321207000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1338642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1338642"],"URL":"https:\/\/doi.org\/10.1137\/20m1338642","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}