On the number of circuits in regular matroids (with connections to lattices and codes). (English) Zbl 1509.05040
Summary: 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 D. R. Karger [in: Discrete algorithms. Proceedings of the 4th annual ACM-SIAM symposium, held at Austin, TX, USA, January 25–27, 1993. Philadelphia, PA: SIAM. 21–30 (1993; Zbl 0801.68124)] 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.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 94B25 | Combinatorial codes |
Keywords:
regular matroids; near-minimum circuits; totally unimodular lattices; near-shortest vectorsCitations:
Zbl 0801.68124Software:
LeibnizReferences:
| [1] | M. Ajtai, The shortest vector problem in \(L_2\) is NP-hard for randomized reductions (extended abstract), in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC ’98, ACM, New York, 1998, pp. 10-19, https://doi.org/10.1145/276698.276705. · Zbl 1027.68609 |
| [2] | N. Alon, Packings with large minimum kissing numbers, Discrete Math., 175 (1997), pp. 249-251, https://doi.org/10.1016/S0012-365X(97)00071-X. · Zbl 0894.52008 |
| [3] | M. Aprile and S. Fiorini, Regular Matroids Have Polynomial Extension Complexity, preprint, arXiv:1909.08539, 2019, https://arxiv.org/abs/1909.08539. |
| [4] | A. Ashikhmin, A. Barg, and S. Vlăduţ, Linear codes with exponentially many light vectors, J. Combin. Theory Ser. A, 96 (2001), pp. 396-399, ŭl(https://www.sciencedirect.com/science/article/pii/S0097316501932066) · Zbl 0980.94026 |
| [5] | A. Barg, Error-Correcting Codes, Lecture notes, University of Maryland, http://www.ece.umd.edu/ abarg/626-2009/notes2005/lecture25.pdf, 2005. |
| [6] | C. Chun and J. G. Oxley, Unavoidable parallel minors of regular matroids, European J. Combin., 32 (2011), pp. 762-774, https://doi.org/10.1016/j.ejc.2011.02.008. · Zbl 1229.05062 |
| [7] | J. H. Conway, N. J. A. Sloane, and E. Bannai, Sphere-Packings, Lattices, and Groups, Springer-Verlag, Berlin, 1987. |
| [8] | M. Dinitz and G. Kortsarz, Matroid secretary for regular and decomposable matroids, 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. · Zbl 1421.68245 |
| [9] | F. V. Fomin, P. A. Golovach, D. Lokshtanov, and S. Saurabh, Covering vectors by spaces: Regular matroids, in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, 2017, pp. 56:1-56:15, https://doi.org/10.4230/LIPIcs.ICALP.2017.56. · Zbl 1441.68106 |
| [10] | F. V. Fomin, P. A. Golovach, D. Lokshtanov, and S. Saurabh, Spanning circuits in regular matroids, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, SIAM, Philadelphia, 2017, pp. 1433-1441, http://dl.acm.org/citation.cfm?id=3039686.3039779. · Zbl 1410.68164 |
| [11] | T. Gavenčiak, D. Král, and S.-I. Oum, Deciding first order properties of matroids, in Automata, Languages, and Programming, 2012, Springer-Verlag, Berlin, pp. 239-250. · Zbl 1367.03022 |
| [12] | J. Geelen, B. Gerards, and G. Whittle, The highly connected matroids in minor-closed classes, Ann. Comb., 19 (2015), pp. 107-123, https://doi.org/10.1007/s00026-015-0251-3. · Zbl 1310.05044 |
| [13] | L. A. Goldberg and M. Jerrum, A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid, in Proceedings of the 38th International Colloquium Conference on Automata, Languages and Programming, Volume Part I, ICALP’11, Springer-Verlag, Berlin, 2011, pp. 521-532, http://dl.acm.org/citation.cfm?id=2027127.2027183. · Zbl 1333.68122 |
| [14] | A. Golynski and J. D. Horton, A polynomial time algorithm to find the minimum cycle basis of a regular matroid, in Algorithm Theory-SWAT 2002, M. Penttonen and E. M. Schmidt, eds., 2002, Springer-Verlag, Berlin, pp. 200-209. · Zbl 1078.68833 |
| [15] | R. Gurjar, T. Thierauf, and N. K. Vishnoi, Isolating a vertex via lattices: Polytopes with totally unimodular faces, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 2018, 74, https://doi.org/10.4230/LIPIcs.ICALP.2018.74. · Zbl 1499.68367 |
| [16] | R. Gurjar and N. K. Vishnoi, On the number of circuits in regular matroids (with connections to lattices and codes), 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. · Zbl 1434.05032 |
| [17] | G. Kalai and N. Linial, On the distance distribution of codes, IEEE Trans. Inform. Theory, 41 (1995), pp. 1467-1472. · Zbl 0831.94019 |
| [18] | R. Kapadia, Finding Shortest Circuits in Binary Matroids, The Matroid Union (blog), http://matroidunion.org/?p=1106, 2014. |
| [19] | D. Karger, A randomized fully polynomial approximation scheme for the all terminal network reliability problem, SIAM J. Comput., 29 (1996), pp. 492-514. · Zbl 0937.05072 |
| [20] | D. R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93, SIAM, Philadelphia, 1993, pp. 21-30, http://dl.acm.org/citation.cfm?id=313559.313605. · Zbl 0801.68124 |
| [21] | N. Kashyap, A decomposition theory for binary linear codes, IEEE Trans. Inform. Theory, 54 (2008), pp. 3035-3058, https://doi.org/10.1109/TIT.2008.924700. · Zbl 1328.94083 |
| [22] | N. Kashyap, Regular Codes Are Not Asymptotically Good, https://ece.iisc.ac.in/ nkashyap/Papers/regular_codes.pdf, 2009. |
| [23] | H.-J. Lai and H. Poon, Cycle cover ratio of regular matroids, European J. Combin., 23 (2002), pp. 1007-1014, http://www.sciencedirect.com/science/article/pii/S0195669802906062. · Zbl 1012.05045 |
| [24] | N. Linial and J. Mosheiff, On the Weight Distribution of Random Binary Linear Codes, CoRR, abs/1806.08392, https://arxiv.org/abs/1806.08392, 2018. · Zbl 1475.94193 |
| [25] | S. Onn, Nonlinear Discrete Optimization: An Algorithmic Theory, Zurich Lectures in Advanced Mathematics, European Mathematical Society Publishing House, Zürich, Switzerland, 2010, https://books.google.co.il/books?id=wzAGMQAACAAJ. · Zbl 1219.90003 |
| [26] | J. G. Oxley, Matroid Theory, Oxford Grad. Texts Math., Oxford University Press, New York, 2006. · Zbl 1115.05001 |
| [27] | P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B, 28 (1980), pp. 305-359, https://doi.org/10.1016/0095-8956(80)90075-1. · Zbl 0443.05027 |
| [28] | A. Subramanian, A polynomial bound on the number of light cycles in an undirected graph, Inform. Process. Lett., 53 (1995), pp. 173-176, http://www.sciencedirect.com/science/article/pii/002001909400202A. · Zbl 1034.68531 |
| [29] | M. Sudan, List decoding: Algorithms and applications, SIGACT News, 31 (2000), pp. 16-27, https://doi.org/10.1145/346048.346049. |
| [30] | C. P. Teo and K. M. Koh, The number of shortest cycles and the chromatic uniqueness of a graph, J. Graph Theory, 16 (1992), pp. 7-15. · Zbl 0770.05064 |
| [31] | K. Truemper, A decomposition theory for matroids. V. Testing of matrix total unimodularity, J. Combin. Theory Ser. B, 49 (1990), pp. 241-281, http://www.sciencedirect.com/science/article/pii/0095895690900304. · Zbl 0646.05014 |
| [32] | K. Truemper, Matroid Decomposition, Leibniz, Plano, TX, 1998. · Zbl 0760.05001 |
| [33] | S. Vlăduţ, Lattices with exponentially large kissing numbers, Moscow J. Combin. Number Theory, 8 (2019), pp. 163-177, https://doi.org/10.2140/moscow.2019.8.163. · Zbl 1448.11124 |
| [34] | Z. Y. Wan, P. Vlachas, P. Koumoutsakos, T. Sapsis, Data-assisted reduced-order modeling of extreme events in complex dynamical systems, PLoS One, 13 (2018), e0197704. |
| [35] | I. B. Yildiz, H. Jaeger, J. Kiebel, Re-visiting the echo state property, Neural Netw., 35 (2012), pp. 1-9. · Zbl 1258.68129 |
| [36] | T. Yamane, H. Numata, J. B. Heroux, N. Kanazawa, S. Takeda, G. Tanaka, T. Nakane, A. Hirose, D. Nakano, Dimensionality reduction by reservoir computing and Its application to IoT edge computing, in Neural Information Processing, ICONIP 2018, Lecture Notes in Comput. Sci. 11301, Springer, Cham, Switzerland, 2018, pp. 635-643. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
