The maximum number of minimal codewords in long codes
Upper bounds on the maximum number of minimal codewords in a binary code follow from the theory of matroids. Random coding provides lower bounds. In this paper, we compare these bounds with analogous bounds for the cycle code of graphs. This problem (in the graphic case) was considered in 1981 by En...
| Huvudupphovsmän: | , , , , |
|---|---|
| Övriga upphovsmän: | |
| Materialtyp: | Journal Article |
| Språk: | English |
| Publicerad: |
2013
|
| Länkar: | https://hdl.handle.net/10356/99215 http://hdl.handle.net/10220/17374 |
| _version_ | 1826114897248780288 |
|---|---|
| author | Alahmadi, A. Aldred, R. E. L. de la Cruz, R. Solé, P. Thomassen, C. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Alahmadi, A. Aldred, R. E. L. de la Cruz, R. Solé, P. Thomassen, C. |
| author_sort | Alahmadi, A. |
| collection | NTU |
| description | Upper bounds on the maximum number of minimal codewords in a binary code follow from the theory of matroids. Random coding provides lower bounds. In this paper, we compare these bounds with analogous bounds for the cycle code of graphs. This problem (in the graphic case) was considered in 1981 by Entringer and Slater who asked if a connected graph with p vertices and q edges can have only slightly more than 2q−p cycles. The bounds in this note answer this in the affirmative for all graphs except possibly some that have fewer than 2p+3log2(3p) edges. We also conclude that an Eulerian (even and connected) graph has at most 2q−p cycles unless the graph is a subdivision of a 4-regular graph that is the edge-disjoint union of two Hamiltonian cycles, in which case it may have as many as 2q−p+p cycles. |
| first_indexed | 2024-10-01T03:46:42Z |
| format | Journal Article |
| id | ntu-10356/99215 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:46:42Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/992152020-03-07T12:31:28Z The maximum number of minimal codewords in long codes Alahmadi, A. Aldred, R. E. L. de la Cruz, R. Solé, P. Thomassen, C. School of Physical and Mathematical Sciences Upper bounds on the maximum number of minimal codewords in a binary code follow from the theory of matroids. Random coding provides lower bounds. In this paper, we compare these bounds with analogous bounds for the cycle code of graphs. This problem (in the graphic case) was considered in 1981 by Entringer and Slater who asked if a connected graph with p vertices and q edges can have only slightly more than 2q−p cycles. The bounds in this note answer this in the affirmative for all graphs except possibly some that have fewer than 2p+3log2(3p) edges. We also conclude that an Eulerian (even and connected) graph has at most 2q−p cycles unless the graph is a subdivision of a 4-regular graph that is the edge-disjoint union of two Hamiltonian cycles, in which case it may have as many as 2q−p+p cycles. 2013-11-07T06:34:47Z 2019-12-06T20:04:45Z 2013-11-07T06:34:47Z 2019-12-06T20:04:45Z 2013 2013 Journal Article Alahmadi, A., Aldred, R., dela Cruz, R., Solé, P., & Thomassen, C. (2013). The maximum number of minimal codewords in long codes. Discrete Applied Mathematics, 161(3), 424-429. 0166-218X https://hdl.handle.net/10356/99215 http://hdl.handle.net/10220/17374 10.1016/j.dam.2012.09.009 en Discrete applied mathematics |
| spellingShingle | Alahmadi, A. Aldred, R. E. L. de la Cruz, R. Solé, P. Thomassen, C. The maximum number of minimal codewords in long codes |
| title | The maximum number of minimal codewords in long codes |
| title_full | The maximum number of minimal codewords in long codes |
| title_fullStr | The maximum number of minimal codewords in long codes |
| title_full_unstemmed | The maximum number of minimal codewords in long codes |
| title_short | The maximum number of minimal codewords in long codes |
| title_sort | maximum number of minimal codewords in long codes |
| url | https://hdl.handle.net/10356/99215 http://hdl.handle.net/10220/17374 |
| work_keys_str_mv | AT alahmadia themaximumnumberofminimalcodewordsinlongcodes AT aldredrel themaximumnumberofminimalcodewordsinlongcodes AT delacruzr themaximumnumberofminimalcodewordsinlongcodes AT solep themaximumnumberofminimalcodewordsinlongcodes AT thomassenc themaximumnumberofminimalcodewordsinlongcodes AT alahmadia maximumnumberofminimalcodewordsinlongcodes AT aldredrel maximumnumberofminimalcodewordsinlongcodes AT delacruzr maximumnumberofminimalcodewordsinlongcodes AT solep maximumnumberofminimalcodewordsinlongcodes AT thomassenc maximumnumberofminimalcodewordsinlongcodes |