Automated conjecturing. I: Fajtlowicz’s Dalmatian heuristic revisited. (English) Zbl 1344.68208
Summary: We discuss a new implementation of, and new experiments with, Fajtlowicz’s Dalmatian conjecture-making heuristic. Our program makes conjectures about relations of real number invariants of mathematical objects. Conjectures in matrix theory, number theory, and graph theory are reported, together with an experiment in using conjectures to automate game play. The program can be used in a way that, by design, advances mathematical research. These experiments suggest that automated conjecture-making can be a useful ability in the design of machines that can perform a variety of tasks that require intelligence.
MSC:
| 68T15 | Theorem proving (deduction, resolution, etc.) (MSC2010) |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
automated conjecturing; automated conjecture-making; mathematical discovery; automated scientific discovery; Dalmatian heuristicReferences:
| [1] | Fajtlowicz, S., On conjectures of Graffiti. V, (Graph Theory, Combinatorics, and Algorithms, vols. 1, 2. Graph Theory, Combinatorics, and Algorithms, vols. 1, 2, Kalamazoo, MI, 1992. Graph Theory, Combinatorics, and Algorithms, vols. 1, 2. Graph Theory, Combinatorics, and Algorithms, vols. 1, 2, Kalamazoo, MI, 1992, Wiley-Intersci. Publ. (1995), Wiley: Wiley New York), 367-376 · Zbl 0843.05065 |
| [2] | DeLaVina, E., Graffiti.pc: a variant of Graffiti, DIMACS Ser. Discret. Math. Theor. Comput. Sci., 69, 71 (2005) · Zbl 1094.05053 |
| [3] | Turing, A., Intelligent machinery, (The Essential Turing (2004)), 395-432 |
| [4] | Simon, H. A.; Newell, A., Heuristic problem solving: the next advance in operations research, Oper. Res., 6, 1, 1-10 (1958) · Zbl 1414.90022 |
| [5] | McCune, W., Solution of the Robbins problem, J. Autom. Reason., 19, 3, 263-276 (1997) · Zbl 0883.06011 |
| [6] | Wang, H., Toward mechanical mathematics, IBM J. Res. Dev., 4, 2-22 (1960) · Zbl 0097.00404 |
| [7] | Fajtlowicz, S., On conjectures of Graffiti, (Proceedings of the First Japan Conference on Graph Theory and Applications. Proceedings of the First Japan Conference on Graph Theory and Applications, Hakone, 1986, vol. 72 (1988)), 113-118 · Zbl 0711.68081 |
| [8] | Fajtlowicz, S., On conjectures of Graffiti. III, (Nineteenth Southeastern Conference on Combinatorics, Graph Theory and Computing. Nineteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, 1988. Nineteenth Southeastern Conference on Combinatorics, Graph Theory and Computing. Nineteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, 1988, Congr. Numer., vol. 66 (1988)), 23-32 · Zbl 0713.05055 |
| [9] | Fajtlowicz, S., On conjectures of Graffiti. II, (Eighteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Eighteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, 1987. Eighteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Eighteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, 1987, Congr. Numer., vol. 60 (1987)), 189-197 · Zbl 0713.05054 |
| [10] | Fajtlowicz, S., On conjectures of Graffiti. IV, (Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1989, vol. 70 (1990)), 231-240 · Zbl 0723.05112 |
| [11] | Cipra, B. A., The sorcerer’s apprentice, Science, 244, 4906, 770 (1989) |
| [12] | DeLaVina, E., Some history of the development of Graffiti, (Graphs and Discovery. Graphs and Discovery, DIMACS Ser. Discret. Math. Theor. Comput. Sci., vol. 69 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 81-118 · Zbl 1096.05049 |
| [13] | Larson, C. E., A survey of research in automated mathematical conjecture-making, (Graphs and Discovery. Graphs and Discovery, DIMACS Ser. Discret. Math. Theor. Comput. Sci., vol. 69 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 297-318 · Zbl 1097.68630 |
| [14] | Lenat, D. B., The ubiquity of discovery, Artif. Intell., 9, 3, 257-285 (1977) |
| [15] | Lenat, D. B., On automated scientific theory formation: a case study using the am program, Mach. Intell., 9, 251-286 (1979) |
| [16] | Lenat, D. B., The nature of heuristics, Artif. Intell., 19, 2, 189-249 (1982) |
| [17] | Davis, R.; Lenat, D. B., Knowledge-Based Systems in Artificial Intelligence (1982), McGraw-Hill International Book Co. · Zbl 0479.68093 |
| [18] | Epstein, S. L., On the discovery of mathematical theorems, (IJCAI (1987)), 194-197 |
| [19] | Epstein, S. L., Learning and discovery: one system’s search for mathematical knowledge, Comput. Intell., 4, 1, 42-53 (1988) |
| [20] | Colton, S.; Bundy, A.; Walsh, T., Automatic concept formation in pure mathematics, (Proceedings of the 16th International Joint Conference on Artificial Intelligence. Proceedings of the 16th International Joint Conference on Artificial Intelligence, IJCAI’99, vol. 2 (1999), Morgan Kaufmann Publishers), 786-791 |
| [21] | Colton, S., Refactorable numbers—a machine invention, J. Integer Seq., 2, 99.1, 2 (1999) · Zbl 1036.11540 |
| [22] | Colton, S., Automated Theory Formation in Pure Mathematics (2002), Springer: Springer Heidelberg · Zbl 1219.68141 |
| [23] | Colton, S., Automated conjecture making in number theory using HR, Otter and Maple, J. Symb. Comput., 39, 5, 593-615 (2005) · Zbl 1126.68100 |
| [24] | Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs: 1 the autographix system, Discrete Math., 212, 1, 29-44 (2000) · Zbl 0947.90130 |
| [25] | Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures, Discrete Math., 276, 1, 81-94 (2004) · Zbl 1031.05068 |
| [26] | Aouchiche, M.; Caporossi, G.; Hansen, P.; Laffay, M., Autographix: a survey, Electron. Notes Discrete Math., 22, 515-520 (2005) · Zbl 1200.05002 |
| [27] | Mélot, H., Facet defining inequalities among graph invariants: the system graphedron, Discrete Appl. Math., 156, 10, 1875-1891 (2008) · Zbl 1152.05380 |
| [28] | Christophe, J.; Dewez, S.; Doignon, J.-P.; Fasbender, G.; Grégoire, P.; Huygens, D.; Labbé, M.; Elloumi, S.; Mélot, H.; Yaman, H., Linear inequalities among graph invariants: using graphedron to uncover optimal relationships, Networks, 52, 4, 287-298 (2008) · Zbl 1151.05334 |
| [29] | Cvetković, D.; Gutman, I., The computer system GRAPH: a useful tool in chemical graph theory, J. Comput. Chem., 7, 5, 640-644 (1986) |
| [30] | Brigham, R.; Dutton, R., INGRID: a software tool for extremal graph theory research, Congr. Numer., 39, 337-352 (1983) · Zbl 0535.05001 |
| [31] | Dutton, R. D.; Brigham, R. C.; Gomez, F., INGRID: a graph invariant manipulator, J. Symb. Comput., 7, 2, 163-177 (1989) · Zbl 0662.05017 |
| [32] | Bagai, R.; Shanbhogue, V.; Żytkow, J. M.; Chou, S.-C., Automatic theorem generation in plane geometry, (Methodologies for Intelligent Systems (1993), Springer), 415-424 |
| [33] | Bagai, R.; Shanbhogue, V.; Zytkow, J. M.; Chou, S.-C., Discovery of geometry theorems: avoiding isomorphic situation descriptions, (Proceedings of the Fifth International Conference on Computing and Information. Proceedings of the Fifth International Conference on Computing and Information, ICCI’93 (1993), IEEE), 354-358 |
| [34] | Wilf, H. S.; Zeilberger, D., Towards computerized proofs of identities, Bull. Am. Math. Soc., 23, 1, 77-83 (1990) · Zbl 0718.05010 |
| [35] | Borwein, J. M.; Bailey, D. H., Mathematics by Experiment: Plausible Reasoning in the 21st Century (2004), AK Peters: AK Peters Natick, MA · Zbl 1083.00001 |
| [36] | Chung, F. R.K., The average distance and the independence number, J. Graph Theory, 12, 2, 229-235 (1988) · Zbl 0644.05029 |
| [37] | Erdős, P.; Saks, M.; Sós, V. T., Maximum induced trees in graphs, J. Comb. Theory, Ser. B, 41, 1, 61-79 (1986) · Zbl 0603.05023 |
| [38] | Fajtlowicz, S., A characterization of radius-critical graphs, J. Graph Theory, 12, 4, 529-532 (1988) · Zbl 0713.05037 |
| [39] | Favaron, O.; Mahéo, M.; Saclé, J.-F., On the residue of a graph, J. Graph Theory, 15, 1, 39-64 (1991) · Zbl 0751.05075 |
| [40] | Griggs, Jerrold R.; Kleitman, Daniel J., Independence and the Havel-Hakimi residue, Discrete Math., 127, 1-3, 209-212 (1994), Graph theory and applications (Hakone, 1990) · Zbl 0805.05082 |
| [41] | Hansen, P.; Hertz, A.; Kilani, R.; Marcotte, O.; Schindl, D., Average distance and maximum induced forest, J. Graph Theory, 60, 1, 31-54 (2009) · Zbl 1182.05049 |
| [42] | Logothetti, D.; Coxeter, H. S.M., An interview with H.S.M. Coxeter, the king of geometry, Two-Year Coll. Math. J., 11, 1, 2-19 (1980) |
| [43] | Fowler, P. W.; Manolopoulos, D. E., An Atlas of Fullerenes (1995), Clarendon Press: Clarendon Press Oxford |
| [44] | Fowler, P. W.; Rogers, K. M.; Fajtlowicz, S.; Hansen, P.; Caporossi, G., Facts and conjectures about fullerene graphs: leapfrog, cylinder and Ramanujan fullerenes, (Algebraic Combinatorics and Applications. Algebraic Combinatorics and Applications, Gößweinstein, 1999 (2001), Springer: Springer Berlin), 134-146 · Zbl 0966.92031 |
| [45] | Fajtlowicz, S.; Larson, C. E., Graph-theoretic independence as a predictor of fullerene stability, Chem. Phys. Lett., 377, 5-6, 485-490 (2003) |
| [46] | Stevanović, D.; Caporossi, G., On the \((1, 2)\)-spectral spread of fullerenes, (Graphs and Discovery. Graphs and Discovery, DIMACS Ser. Discret. Math. Theor. Comput. Sci., vol. 69 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 365-370 · Zbl 1097.05028 |
| [47] | Daugherty, S. M., Independent sets and closed-shell independent sets of fullerenes (2010), AAINR66829 |
| [48] | Mallion, R. B.; Rouvray, D. H., The golden jubilee of the Coulson-Rushbrooke pairing theorem, J. Math. Chem., 5, 1, 1-21 (1990) |
| [49] | Peeters, A., GrInvIn - a software framework for education and research in graph theory (2008), Ghent University, Thesis (Ph.D.) |
| [50] | Peeters, A.; Coolsaet, K.; Brinkmann, G.; Van Cleemput, N.; Fack, V., GrInvIn in a nutshell, J. Math. Chem., 45, 2, 471-477 (2009) · Zbl 1194.92095 |
| [51] | Horn, R. A.; Johnson, C. R., Matrix Analysis (2012), Cambridge University Press |
| [52] | Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1979), Oxford University Press · Zbl 0423.10001 |
| [53] | Richstein, J., Verifying the Goldbach conjecture up to \(4 \cdot 10^{14}\), Math. Comput., 70, 236, 1745-1749 (2001) · Zbl 0989.11050 |
| [54] | Crandall, R. E.; Pomerance, C., Prime Numbers: A Computational Perspective, vol. 182 (2005), Springer · Zbl 1088.11001 |
| [55] | Rosser, B., Explicit bounds for some functions of prime numbers, Am. J. Math., 63, 1, 211-232 (1941) · JFM 67.0129.03 |
| [56] | Rosser, J. B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Ill. J. Math., 6, 6-9 (1962) |
| [57] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs, Monogr. Textb. Pure Appl. Math., vol. 208 (1998), Marcel Dekker Inc.: Marcel Dekker Inc. New York · Zbl 0890.05002 |
| [58] | West, D. B., Introduction to Graph Theory (2001), Prentice Hall |
| [59] | Pepper, R., On the annihilation number of a graph, Recent Adv. Appl. Math. Comput. Inf. Sci., 1, 217-220 (2009) |
| [60] | Larson, C. E.; Pepper, R., Graphs with equal independence and annihilation numbers, Electron. J. Comb., 18, 1 (2011) · Zbl 1238.05198 |
| [62] | Garey, Michael R.; Johnson, David S., Computers and intractability, (A Guide to the Theory of NP-Completeness. A Guide to the Theory of NP-Completeness, Ser. Books Math. Sci. (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco, Calif.) · Zbl 0411.68039 |
| [63] | Larson, C. E., A note on critical independence reductions, Bull. Inst. Comb. Appl., 51, 34-46 (2007) · Zbl 1135.05051 |
| [64] | Larson, C. E., The critical independence number and an independence decomposition, Eur. J. Comb., 32, 2, 294-300 (2011) · Zbl 1230.05226 |
| [65] | DeLaVina, E.; Larson, C. E., A parallel algorithm for computing the critical independence number and related sets, Ars Math. Contemp. (2015), in press |
| [66] | Angel, E.; Campigotto, R.; Laforest, C., A new lower bound on the independence number of graphs, Discrete Appl. Math., 161, 6, 847-852 (2013) · Zbl 1262.05114 |
| [67] | Lovász, L., On the shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021 |
| [68] | Knuth, Donald E., The sandwich theorem, Electron. J. Comb., 1, Article 1 pp. (1994), 48 pp. (electronic) · Zbl 0810.05065 |
| [69] | Lovász, L., Semidefinite programs and combinatorial optimization, (Recent Advances in Algorithms and Combinatorics. Recent Advances in Algorithms and Combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11 (2003), Springer: Springer New York), 137-194 · Zbl 1040.90032 |
| [70] | Read, R. C.; Wilson, R. J., An Atlas of Graphs, vol. 21 (1998), Clarendon Press: Clarendon Press Oxford · Zbl 0908.05001 |
| [71] | Bollobás, Béla, Random Graphs, Cambridge Stud. Adv. Math., vol. 73 (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0979.05003 |
| [72] | Gale, D., A curious Nim-type game, Am. Math. Mon., 876-879 (1974) · Zbl 0295.90045 |
| [73] | DeLaVina, E.; Pepper, R.; Waller, W., Independence, radius and Hamiltonian paths, MATCH Commun. Math. Comput. Chem., 58, 2, 481-510 (2007) · Zbl 1141.05042 |
| [74] | Gould, R. J., Updating the Hamiltonian problem—a survey, J. Graph Theory, 15, 2, 121-157 (1991) · Zbl 0746.05039 |
| [75] | Gould, R. J., Advances on the Hamiltonian problem—a survey, Graphs Comb., 19, 1, 7-52 (2003) · Zbl 1024.05057 |
| [76] | Deming, R. W., Independence numbers of graphs—an extension of the Koenig-Egervary theorem, Discrete Math., 27, 1, 23-33 (1979) · Zbl 0404.05034 |
| [77] | Sterboul, F., A characterization of the graphs in which the transversal number equals the matching number, J. Comb. Theory, Ser. B, 27, 2, 228-229 (1979) · Zbl 0415.05032 |
| [78] | Lovász, L., Ear-decompositions of matching-covered graphs, Combinatorica, 3, 1, 105-117 (1983) · Zbl 0516.05047 |
| [79] | Bourjolly, J.-M.; Pulleyblank, W. R., König-Egerváry graphs, 2-bicritical graphs and fractional matchings, Discrete Appl. Math., 24, 1, 63-82 (1989) · Zbl 0684.05036 |
| [80] | Hardy, G. H., A Mathematician’s Apology (1940), The University Press · Zbl 0025.19301 |
| [81] | Colton, S.; Bundy, A.; Walsh, T., On the notion of interestingness in automated mathematical discovery, Int. J. Hum.-Comput. Stud., 53, 3, 351-375 (2000) · Zbl 1011.68621 |
| [82] | Langely, P.; Simon, H. A.; Bradshaw, G. L.; Zytkow, J. M., Scientific Discovery: Computational Explorations of the Creative Process (1987), MIT Press: MIT Press Cambridge, MA |
| [83] | Wang, H., Computer theorem proving and artificial intelligence, (Computation, Logic, Philosophy (1990), Springer), 63-75 |
| [84] | Stein, W., Sage: open source mathematical software (version 2.10.2), The Sage group (2008) |
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.
