Irreducible subcube partitions. (English) Zbl 07808904
Summary: A subcube partition is a partition of the Boolean cube \(\{0,1\}^n\) into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are singletons and the entire partition. A subcube partition is tight if it “mentions” all coordinates.
We study extremal properties of tight irreducible subcube partitions: minimal size, minimal weight, maximal number of points, maximal size, and maximal minimum dimension. We also consider the existence of homogeneous tight irreducible subcube partitions, in which all subcubes have the same dimensions. We additionally study subcube partitions of \(\{0, \dots, q-1\}^n\), and partitions of \(\mathbb{F}_2^n\) into affine subspaces, in both cases focusing on the minimal size.
Our constructions and computer experiments lead to several conjectures on the extremal values of the aforementioned properties.
We study extremal properties of tight irreducible subcube partitions: minimal size, minimal weight, maximal number of points, maximal size, and maximal minimum dimension. We also consider the existence of homogeneous tight irreducible subcube partitions, in which all subcubes have the same dimensions. We additionally study subcube partitions of \(\{0, \dots, q-1\}^n\), and partitions of \(\mathbb{F}_2^n\) into affine subspaces, in both cases focusing on the minimal size.
Our constructions and computer experiments lead to several conjectures on the extremal values of the aforementioned properties.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W20 | Randomized algorithms |
| 51E23 | Spreads and packing problems in finite geometry |
| 94D10 | Boolean functions |
Software:
JBoolReferences:
| [1] | S. V. Agievich. Bent rectangles. In Boolean Functions in Cryptology and Infor-mation Security, volume 18 of NATO Sci. Peace Secur. Ser. D: Inf. Commun. Secur., 2008. · Zbl 1167.94004 |
| [2] | Ron Aharoni and Nathan Linial. Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A, 43(2):196-204, 1986. doi:10.1016/0097-3165(86)90060-9. · Zbl 0611.05045 · doi:10.1016/0097-3165(86)90060-9 |
| [3] | A. Blokhuis and A. E. Brouwer. Blocking sets in Desarguesian projective planes. Bulletin of the London Mathematical Society, 18(2):132-134, 1986. doi:10.1112/blms/18.2.132. · Zbl 0563.05016 · doi:10.1112/blms/18.2.132 |
| [4] | Sven Baumer, Juan Luis Esteban, and Jacobo Torán. Minimally unsatisfiable CNF formulas. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 74:190-192, 2001. · Zbl 1018.68075 |
| [5] | Marc A. Berger, Alexander Felzenbaum, and Aviezri S. Fraenkel. Irreducible disjoint covering systems (with an application to Boolean algebra). Dis-crete Appl. Math., 29(2-3):143-164, 1990. First International Colloquium on Pseudo-Boolean Optimization and Related Topics (Chexbres, 1987). doi: 10.1016/0166-218X(90)90140-8. · Zbl 0729.11006 · doi:10.1016/0166-218X(90)90140-8 |
| [6] | John Bamberg, Yuval Filmus, Ferdinand Ihringer, and Sascha Kurz. Affine vector space partitions. Designs, Codes and Cryptography, 2023. doi:10. 1007/s10623-023-01263-z. · doi:10.1007/s10623-023-01263-z |
| [7] | Y. Brandman, A. Orlitsky, and J. Hennessy. A spectral lower bound technique for the size of decision trees and two-level AND/OR circuits. IEEE Trans. Comput., 39(2):282287, feb 1990. doi:10.1109/12.45216. · doi:10.1109/12.45216 |
| [8] | Yves Crama and Peter L. Hammer. Boolean functions, volume 142 of Ency-clopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2011. Theory, algorithms, and applications. doi:10.1017/ CBO9780511852008. · Zbl 1237.06001 · doi:10.1017/CBO9780511852008 |
| [9] | Vašek Chvátal and Endre Szemerédi. Many hard examples for resolution. J. Assoc. Comput. Mach., 35(4):759-768, 1988. doi:10.1145/48014.48016. · Zbl 0712.03008 · doi:10.1145/48014.48016 |
| [10] | G. Davydov and I. Davydova. Dividing formulas and polynomial classes for satisfiability. In SAT98, 2nd Workshop on the Satisfiability Problem, page 1221, 1998. |
| [11] | Gennady Davydov, Inna Davydova, and Hans Kleine Büning. An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF. Ann. Math. Artificial Intelligence, 23(3-4):229-245, 1998. doi:10.1023/A: 1018924526592. · Zbl 0913.68090 · doi:10.1023/A:1018924526592 |
| [12] | Ehud Friedgut, Jeff Kahn, and Avi Wigderson. Computing graph properties by randomized subcube partitions. In José D. P. Rolim and Salil Vadhan, editors, Randomization and Approximation Techniques in Computer Science, pages 105-113, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. · Zbl 1028.68567 |
| [13] | Rodney Forcade. Smallest maximal matchings in the graph of the d-dimensional cube. J. Combinatorial Theory Ser. B, 14:153-156, 1973. doi: 10.1016/0095-8956(73)90059-2. · Zbl 0261.05123 · doi:10.1016/0095-8956(73)90059-2 |
| [14] | Matthew Gwynne and Oliver Kullmann. Towards a theory of good SAT rep-resentations. arXiv:1302.4421. · Zbl 1408.68077 |
| [15] | Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic commu-nication vs. partition number. SIAM J. Comput., 47(6):2435-2450, 2018. doi:10.1137/16M1059369. · Zbl 1409.68115 · doi:10.1137/16M1059369 |
| [16] | Kazuo Iwama. Complementary approaches to CNF Boolean equations. In Discrete algorithms and complexity (Kyoto, 1986), volume 15 of Perspect. Comput., pages 223-236. Academic Press, Boston, MA, 1987. · Zbl 0643.68079 |
| [17] | Kazuo Iwama. CNF-satisfiability test by counting and polynomial average time. SIAM J. Comput., 18(2):385-391, 1989. doi:10.1137/0218026. · Zbl 0674.68034 · doi:10.1137/0218026 |
| [18] | Hans Kleine Büning. On subclasses of minimal unsatisfiable formulas. Discrete Appl. Math., 107(1-3):83-98, 2000. Boolean functions and related problems. doi:10.1016/S0166-218X(00)00245-6. · Zbl 0965.03016 · doi:10.1016/S0166-218X(00)00245-6 |
| [19] | Andrzej P. Kisielewicz. Partitions and balanced matchings of an n-dimensional cube. European J. Combin., 40:93-107, 2014. doi:10.1016/j.ejc.2014.02. 005. · Zbl 1297.05048 · doi:10.1016/j.ejc.2014.02.005 |
| [20] | Andrzej P. Kisielewicz. On the structure of cube tiling codes. European Jour-nal of Combinatorics, 89:103168, 2020. doi:10.1016/j.ejc.2020.103168. · Zbl 1479.52033 · doi:10.1016/j.ejc.2020.103168 |
| [21] | Andrzej P. Kisielewicz. Private communication, 2023. |
| [22] | Ivan Korec. Irreducible disjoint covering systems. Acta Arith., 44(4):389-395, 1984. doi:10.4064/aa-44-4-389-395. · Zbl 0519.10002 · doi:10.4064/aa-44-4-389-395 |
| [23] | Andrzej P. Kisielewicz and Krzysztof Przes lawski. Polyboxes, cube tilings and rigidity. Discrete Comput. Geom., 40(1):1-30, 2008. doi:10.1007/ s00454-007-9005-2. · Zbl 1147.52009 · doi:10.1007/s00454-007-9005-2 |
| [24] | Oliver Kullmann. An application of matroid theory to the SAT problem. In 15th Annual IEEE Conference on Computational Complexity (Florence, 2000), pages 116-124. IEEE Computer Soc., Los Alamitos, CA, 2000. doi: 10.1109/CCC.2000.856741. · doi:10.1109/CCC.2000.856741 |
| [25] | Oliver Kullmann. The combinatorics of conflicts between clauses. In Enrico Giunchiglia and Armando Tacchella, editors, Theory and Applications of Sat-isfiability Testing, pages 426-440, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. · Zbl 1204.68202 |
| [26] | Oliver Kullmann and Xishun Zhao. On Davis-Putnam reductions for min-imally unsatisfiable clause-sets. Theoret. Comput. Sci., 492:70-87, 2013. doi:10.1016/j.tcs.2013.04.020. · Zbl 1296.03010 · doi:10.1016/j.tcs.2013.04.020 |
| [27] | Oliver Kullmann and Xishun Zhao. Unsatisfiable hitting clause-sets with three more clauses than variables. arXiv:1604.01288. · Zbl 1296.03010 |
| [28] | J. C. Lagarias and P. W. Shor. Cube-tilings of R n and nonlinear codes. Discrete Comput. Geom., 11(4):359-391, 1994. doi:10.1007/BF02574014. · Zbl 0804.52013 · doi:10.1007/BF02574014 |
| [29] | Shaohan Ma and Dongmin Liang. A polynomial-time algorithm for reducing the number of variables in MAX SAT problem. Sci. China Ser. E, 40(3):301-311, 1997. doi:10.1007/BF02916605. · Zbl 0881.68086 · doi:10.1007/BF02916605 |
| [30] | A. L. Perezhogin. On special perfect matchings in a Boolean cube. Diskretn. Anal. Issled. Oper. Ser. 1, 12(4):51-59, 2005. · Zbl 1249.05312 |
| [31] | Tomáš Peitl and Stefan Szeider. Are hitting formulas hard for resolution? Dis-crete Applied Mathematics, 337:173-184, 2023. doi:10.1016/j.dam.2023. 05.003. · Zbl 07696121 · doi:10.1016/j.dam.2023.05.003 |
| [32] | R. Rado. Note on the transfinite case of Hall’s theorem on representatives. J. London Math. Soc., 42:321-324, 1967. doi:10.1112/jlms/s1-42.1.321. · Zbl 0159.01803 · doi:10.1112/jlms/s1-42.1.321 |
| [33] | Yu. V. Tarannikov. On the existence of Agievich-primitive partitions. Diskretn. Anal. Issled. Oper. Ser. 1, 29(4):104-123, 2022. · Zbl 1508.51002 |
| [34] | Yu. V. Tarannikov. Private communication, 2023. |
| [35] | D. J. A. Welsh. Generalized versions of Hall’s theorem. J. Combinatorial Theory Ser. B, 10:95-101, 1971. doi:10.1016/0095-8956(71)90069-4. · Zbl 0231.05005 · doi:10.1016/0095-8956(71)90069-4 |
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.
