The Optimist: Towards Fully Automated
Graph Theory Research

A major advancement in filtering meaningful conjectures emerged with Fajtlowicz’s Graffiti program in the 1980s. Graffiti generated inequalities between real-valued functions (invariants) on mathematical objects, primarily within graph theory. The program operated on a database of graphs, aiming to identify inequalities of the form:

where $\alpha$ is a target invariant and $f(\text{invariants})$ is an expression involving other invariants, often in the form of sums, products, or more complex combinations constructed through an arithmetic expression tree. For example, Graffiti might conjecture an inequality such as $\alpha\leq\frac{n}{2}$, where $\alpha$ represents the independence number of a graph, and $n$ denotes the graph’s order (number of vertices).

The challenge of distinguishing nontrivial conjectures from trivial ones persisted. To address this, Graffiti introduced the innovative Dalmatian heuristic, a technique for refining conjectures based on their significance and validity across known examples. The Dalmatian heuristic operates with two primary criteria:

Fajtlowicz described the heuristic’s process as follows:

“The program keeps track of conjectures made in the past, and when it encounters a new candidate for a conjecture, it first verifies whether an example in the database shows that the conjecture does not follow from earlier conjectures. If no such example exists, the conjecture is rejected as non-informative. If one exists, the program proceeds with testing the conjecture’s correctness, and then checks whether the conjecture should be rejected by other heuristics. If accepted, the list of conjectures is revised, and less informative conjectures are removed from the list and stored separately in case the new conjecture is refuted later.” [5]

The Dalmatian heuristic not only reduced the number of conjectures but also enhanced their relevance by prioritizing conjectures that advanced current knowledge. When applied to identifying bounds on invariants, particularly those of active research interest, Graffiti produced conjectures where existing theory offered insufficient predictions for invariant values. Such conjectures, if extending current understanding, were considered significant. Indeed, Graffiti generated numerous conjectures that contributed substantially to both graph theory [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31] and mathematical chemistry [32, 33, 34, 35, 36, 37, 38, 39]. For further details on Graffiti and the Dalmatian heuristic, see [1, 40].

Building upon the Dalmatian heuristic, DeLaViña’s Graffiti.pc and Larson’s Conjecturing programs extended automated conjecturing in graph theory and beyond. Developed during DeLaViña’s PhD studies under Fajtlowicz, Graffiti.pc retained the original focus on graph theory while significantly expanding computational capabilities. Unlike its predecessor, which handled datasets with a few hundred graphs, Graffiti.pc was implemented in C++ to work with much larger datasets, often comprising millions of graphs, and sometimes required computational clusters for efficient conjecture generation and testing. With applications in both education and research, Graffiti.pc notably contributed to domination theory, leading to important results in this field [41, 42, 43]. Despite these advances, increasing the dataset size did not always yield higher quality conjectures, as both Graffiti and Graffiti.pc were limited by the absence of certain small, special graphs in their datasets, which could serve as counterexamples to conjectures.

Recognizing the importance of selecting relevant datasets, Larson’s Conjecturing program introduced a more flexible framework capable of generating conjectures across various mathematical disciplines, while still implementing the Dalamatian heuristic. Although the focus remained on inequalities involving graph invariants, Conjecturing allowed for user-defined objects, invariants, and relations, expanding beyond graph theory into fields such as number theory and algebra. This adaptability enabled researchers to tailor the conjecture generation process for specific problems and customize parameters to guide the program towards nontrivial results.

TxGraffiti [1] is an automated conjecturing program maintained by the author that focuses on generating meaningful conjectures in graph theory by leveraging principles similar to Fajtlowicz’s Graffiti, particularly the emphasis on the mathematical strength of statements. However, TxGraffiti applies linear optimization models to a precomputed tabular dataset of graph invariants, generating both upper and lower bounds for target invariants by solving optimization problems that minimize or maximize the discrepancy between a target invariant and an expression involving other invariants. Specifically, to establish an upper bound, TxGraffiti minimizes a linear objective subject to constraints that enforce the inequality across all graphs meeting certain boolean conditions. This approach results in inequalities of the form $\alpha\leq m\cdot f(\text{invariants})+b$, where $\alpha$ is the target invariant, $f(\text{invariants})$ represents other graph properties, and $m$ and $b$ are optimized scalars. Similarly, lower bounds are generated by maximizing this objective under reversed constraints, offering a dual approach to bounding invariants within the dataset.

To prioritize conjectures, TxGraffiti employs the touch number heuristic, which measures how often an inequality holds as an equality across different graphs, thus reflecting the conjecture’s strength and relevance. Conjectures with high touch numbers are prioritized, as they suggest a tighter relationship between invariants. Additionally, TxGraffiti uses the static-Dalmatian heuristic, a refinement of the original Dalmatian heuristic, to eliminate redundant conjectures by filtering out those that can be derived from others via transitivity. This heuristic operates on a fixed set of conjectures, iteratively discarding any conjecture that does not introduce new information relative to previously accepted ones. Together, the optimization methods and heuristics used by TxGraffiti have led to several published results in graph theory (see [44, 45, 46, 47, 48, 49]).

For other notable automated conjecturing systems that have contributed to various mathematical domains, see Lenat’s AM [50, 51, 52], Epstein’s Graph Theorist [53], Colton’s HR system [54, 55, 56], Hansen and Caporossi’s AutoGraphiX (AGX) [57, 58], and Mélot’s GraPHedron and its successor PHOEG [59, 60].

At the core of the Optimist agent’s framework is an initial set of structured inputs that constitute its foundational knowledge, forming the basis for conjecture formulation. This setup includes three primary components: a collection of graphs, a dictionary of computable graph invariant functions, and a repository of known theorems. Each graph in the collection provides a distinct context in which relationships between invariants can be examined, thereby supplying diverse examples to inform potential conjectures.

The dictionary of invariants encompasses functions that compute essential properties of each graph, such as independence number, vertex count, and bipartiteness, which serve as key components in constructing conjectures. These invariants provide quantifiable data points that the Optimist utilizes in identifying relationships and generating bounds.

Furthermore, Optimist references a repository of known theorems to prevent the generation of redundant conjectures that merely replicate established results. This enables the system to focus on conjectures that extend beyond current knowledge, prioritizing relationships that are novel or have yet to be formally proven.

To facilitate conjecture generation and analysis, Optimist employs several internal data structures. The framework organizes conjectures into separate lists of upper and lower bounds for each target invariant, consolidating these conjectures into a comprehensive collection. This approach allows for efficient retrieval and streamlined analysis, supporting a systematic examination of conjectures across various graph invariants.

To systematically investigate relationships between graph invariants, the Optimist framework constructs a tabular dataset, termed its knowledge base, or knowledge table (implemented as a Pandas DataFrame). In this structure, each row corresponds to a unique graph instance, while each column represents a specific invariant or boolean property. This organization enables efficient data access and facilitates conjecture generation by allowing the framework to process invariant data in a manner akin to feature-based analysis in machine learning models. Analogous to how learning models identify patterns across features, Optimist identifies potential conjectures by exploring relationships among these stored invariants.

A primary advantage of this knowledge base is that it stores all invariant values upon initial computation, obviating the need for recomputation during conjecture generation and validation. Given that calculating graph invariants can be computationally intensive, this storage approach significantly reduces the overhead of conjecture generation, streamlining the exploration process. By storing these invariant values centrally, Optimist can efficiently retrieve relationships among invariants in real time, thereby facilitating more dynamic conjecture formulation.

This knowledge base thus functions as a structured “memory” for the Optimist agent, enabling it to effectively leverage previously computed data in the same way a reasoning system might recall facts to inform subsequent decision-making. Through this design, Optimist not only enhances computational efficiency but also supports a more comprehensive exploration of graph-theoretic relationships.

The Optimist framework employs a mixed-integer programming (MIP) approach to generate conjectures establishing upper and lower bounds on a target invariant. Unlike TxGraffiti, which typically relates a single invariant to the target invariant, Optimist formulates conjectures by considering linear combinations of multiple invariants under various boolean conditions. The Optimist agent simultaneously seeks both upper and lower bounds, and in cases where bounds converge, it identifies exact equalities.

To produce meaningful bounds on a target invariant, Optimist solves two MIP formulations that optimize for tight upper and lower bounds. The framework emphasizes maximizing instances where each bound holds as an equality, ensuring conjectures that are not only accurate but also sharp. This focus on equality instances aligns with the goal of producing conjectures that provide informative bounds on extreme values of the target invariant.

Let $\alpha$ denote the target invariant, and let $f(\text{invariants})$ represent a linear combination of other invariants. The bounds we seek can be expressed as:

where $f(\text{invariants})$ is a weighted sum of invariants with weights that maximize equality conditions across a dataset derived from the Optimist agent’s knowledge base. Let $Y_{i}$ represent the target invariant for each graph $i$, and let $\mathbf{X}_{i}$ represent the selected invariants of graph $i$. The MIP seeks weights $w_{1},w_{2},\dots,w_{k}$ and an intercept $b$ to optimize the following constraints:

For the upper bound, we solve:

Binary variables $z_{i}^{\text{upper}}$ are introduced to indicate equality, expressed by the constraint:

where $M$ is a large constant that relaxes the equality requirement when $z_{i}^{\text{upper}}=0$.

Similarly, for the lower bound, we solve:

Binary variables $z_{i}^{\text{lower}}$ are introduced, with constraints defined as:

The objective function maximizes the total number of equality instances:

This formulation identifies optimal weights and intercepts for the bounds, yielding:

When the solutions for upper and lower bounds converge, we obtain an equality:

Otherwise, the inequalities define a bounded range for $\alpha$, delineating the behavior of the target invariant over the graph dataset.

The MIP is implemented in Python using the PuLP library, providing a flexible and efficient platform for solving these models; see Appendix A or our GitHub repository²²2https://github.com/RandyRDavila/The-Optimist/tree/main. Through this optimization approach, Optimist generates conjectures that not only align with observed data but also enhance interpretability by prioritizing equality instances, thus identifying sharp bounds for the target invariant.

The Optimist framework explores diverse combinations of invariants systematically, aiming to generate a comprehensive set of conjectures for each target invariant. For each target invariant, Optimist constructs bounds by iterating through pairs of explanatory invariants, each conditioned by a single boolean property. This process is managed through the function make_all_linear_conjectures, which organizes these combinations to generate upper and lower bounds; see Listing 1.

The function make_all_linear_conjectures performs the following operations:

• •

  For each pair of invariants, it applies all specified boolean properties, ensuring that the conjecture generation covers a broad space of possible relationships.

• •

  Within each pair, the target invariant is constrained to avoid redundancies, ensuring that neither explanatory invariant directly corresponds to the target.

• •

  The function calls the MIP-based make_linear_conjectures function to compute bounds on the target invariant, yielding a candidate set of upper and lower conjectures.

The output of this procedure is a set of candidate conjectures for each target invariant, reflecting a systematic approach to exploring multi-invariant relationships under varied boolean conditions.

This function thus enables Optimist to generate bounds across a systematic range of invariant combinations, producing a foundational set of conjectures that can then be refined and prioritized based on empirical support and mathematical relevance.

After invoking the make_all_linear_conjectures function on a target invariant, the Optimist agent typically produces extensive lists of potential conjectures—often in the hundreds—depending on the numerical and boolean properties considered. To identify and prioritize conjectures with strong empirical backing, Optimist applies the Hazel Heuristic, a filtering process centered on each conjecture’s touch number.

The touch number of a conjectured inequality is defined as the number of graphs in the Optimist knowledge base for which the inequality holds as an equality. A high touch number suggests that the conjectured bound is not only generally valid but also sharp for a significant subset of graphs, indicating a potentially fundamental relationship between the target invariant and the explanatory invariants. High-touch conjectures are, therefore, more likely to capture structural properties of graph invariants and yield insights beyond loose or incidental bounds.

The Hazel Heuristic applies three successive steps:

1. 1.

   Deduplication: Removes duplicate conjectures to ensure the uniqueness of bounds.

2. 2.

   Filtering: Discards conjectures with touch numbers below a specified threshold, removing bounds that lack consistent sharpness across the dataset.

3. 3.

   Sorting: Orders conjectures in descending order of touch number, bringing conjectures with the highest empirical support to the forefront.

By prioritizing conjectures with the highest touch numbers, the Hazel Heuristic ensures that the most empirically significant conjectures are advanced for further analysis. This ranking approach confers several advantages:

• •

  Relevance: Conjectures with high touch numbers are more likely to represent tight bounds, making them strong candidates for formal validation or proof.

• •

  Robustness: A high touch number indicates that a conjecture’s bound is consistently representative across diverse graph structures, enhancing its robustness and potential generalizability.

• •

  Informational Value: High-touch conjectures highlight areas where graph invariants exhibit strong interactions, offering insights into fundamental invariant relationships.

Through the Hazel Heuristic, Optimist focuses on conjectures with maximal empirical evidence, refining the conjecture set to emphasize inequalities with the greatest potential for meaningful mathematical contribution.

The Morgan Heuristic identifies and removes redundant conjectures, prioritizing the most general conjectures with broad applicability. Specifically, a conjecture is flagged as redundant if it shares the same conclusion as another but is based on a more specific (less general) hypothesis. By focusing on generality, this heuristic ensures that the final set of conjectures includes only the most powerful and widely applicable statements.

For example, consider the two conjectures in Listing 3. Every tree is a bipartite graph, but not every bipartite graph is a tree. Therefore, Conjecture 4, which applies to all connected bipartite graphs, is more general than Conjecture 2, which applies only to trees. As such, Conjecture 2 is discarded in favor of Conjecture 4.

In practice, the generality of a conjecture’s hypothesis is determined by counting the number of graphs in the Optimist knowledge base that satisfy the hypothesis. If one hypothesis applies to a larger subset of graphs than another, it is considered more general. This count-based approach, though heuristic, provides a practical method for determining generality even when relationships between graph classes are not fully defined; see the implementation in Listing 4.

The key steps in the Morgan Heuristic are as follows:

1. 1.

   Identify Redundancy: Conjectures are flagged as redundant if they share identical conclusions but differ in hypothesis generality.

2. 2.

   Assess Generality: For each pair of conjectures with the same conclusion, the conjecture with a hypothesis that applies to a larger subset of graphs is considered more general, based on empirical counts from the Optimist dataset.

3. 3.

   Comparison and Removal: If one conjecture is a generalization of another, the less general conjecture is removed.

4. 4.

   Refinement: This process iteratively refines the conjecture set, ensuring that only unique, maximally general conjectures remain.

Applying the Morgan Heuristic yields a refined list of conjectures that are maximally general and devoid of redundancy. This reduction not only simplifies the conjecture set but also enhances its theoretical strength, highlighting statements with the broadest potential applicability.

To further refine the conjecture set, the Optimist agent employs two selective heuristics: the weak-smokey and strong-smokey heuristics. Both heuristics reduce redundancy by examining the set of sharp graphs—instances where each conjectured inequality holds as an equality—though each applies distinct criteria to retain only conjectures that offer unique insights.

The weak-smokey heuristic iterates through conjectures in descending order of touch number, retaining conjectures that introduce new sharp graphs not already covered by previously selected conjectures. This approach prioritizes conjectures with complementary equality instances, achieving a balance between inclusiveness and informativeness. By focusing on unique sharp instances, weak-smokey substantially reduces the initial conjecture set while maintaining broad empirical relevance.

In contrast, the strong-smokey heuristic applies a stricter criterion, requiring that each retained conjecture covers a strict superset of sharp graphs compared to any previously selected conjecture. This process begins with the conjecture having the highest touch number, then adds conjectures only if they introduce strictly new equality instances. By requiring that each new conjecture expands the set of sharp graphs, strong-smokey yields a minimal set of conjectures, often halving the number retained by weak-smokey. This minimality ensures that only conjectures providing the most unique insights are retained.

Applying either the weak-smokey or strong-smokey heuristic significantly reduces the conjecture set for a given target invariant, typically retaining only four or five conjectures from an initially large list. As a stricter filter, strong-smokey produces a subset of the conjectures selected by weak-smokey. It is employed when Optimist seeks to retain only the most general and minimal set of conjectures, emphasizing statements that provide the greatest informational value.

The Optimist agent is designed as an iterative system for conjecture generation, filtering, and continuous refinement based on new information. At the core of this process is the use of mixed-integer programming (MIP) to generate conjectures. Using combinations of graph invariants, Optimist generates potential upper and lower bounds for a target invariant. Each conjecture is initially stored in memory, organized by target invariant.

Given the potentially large number of conjectures generated, Optimist applies a multi-stage filtering process to ensure that only the most informative and robust conjectures are retained. The first phase employs the Hazel heuristic, which prioritizes conjectures with the highest empirical relevance by sorting them according to touch number—a measure of how frequently each conjecture holds as an equality across the dataset. This step ensures that Optimist focuses on conjectures that provide tight bounds for the target invariant.

Next, the Morgan heuristic is applied to remove redundant conjectures with more restrictive hypotheses that do not contribute new insights over more general conjectures with the same conclusion. This heuristic ensures the final conjecture set retains only the most widely applicable statements.

A final layer of filtering applies either the strong-smokey or weak-smokey heuristic, depending on the desired strictness. The weak-smokey heuristic favors inclusiveness, retaining conjectures that add new sharp instances, while the strong-smokey heuristic strictly selects conjectures that cover strictly broader sets of sharp graphs. This stage produces a minimal, highly informative set of conjectures, prioritizing those with the broadest empirical applicability – essentially equivalent to an unpublished version of TxGraffiti called TxGraffiti II, which is available as an interactive website³³3https://txgraffiti.streamlit.app/Generate_MIP_Conjectures.

The initial setup for Optimist included three of the smallest nontrivial connected graph structures: the complete graphs $K_{2}$ and $K_{3}$ and the path graph $P_{3}$, as shown in Figure 2. The agent was configured with a selection of invariants relevant to conjecturing $\alpha(G)$, including the order $n$, minimum degree $\delta$, maximum degree $\Delta$, matching number $\mu$, and minimum maximal matching number $\mu^{*}$, among others. With this setup, Optimist could explore a variety of relationships between $\alpha(G)$ and these properties.

From this minimal configuration, Optimist generated an initial series of conjectures aimed at establishing upper and lower bounds for $\alpha(G)$. The resulting conjectures were broad, reflecting the limited dataset and covering a variety of possible inequalities. This initial series included nearly 60 conjectures, illustrating the heuristic’s dependency on dataset size and the need for further refinement to isolate the most significant bounds.

Following the initial conjecture set, the user identified conjectures that could be invalidated by counterexamples. For instance, the conjecture presented in Listing 7 was shown to be false for the path graph $P_{6}$.

Noting this counterexample, the user informed the Optimist agent of $P_{6}$, prompting the agent to update its knowledge base and regenerate its conjecture set.

With each new graph added, Optimist refined its conjecture set, retaining inequalities that consistently held across the expanded dataset and discarding or modifying those that failed to generalize. This interactive process continued over multiple iterations, with Optimist generating conjectures and the user acting as a Pessimist by providing counterexamples. Each update expanded the agent’s knowledge base, enabling it to generate more reliable conjectures. Figure 3 shows the set of counterexample graphs introduced during this process.

This iterative refinement process allowed Optimist to progressively narrow down the set of plausible bounds on $\alpha(G)$, adapting its conjectures in response to new data. The user’s counterexamples acted as a form of hypothesis testing, whereby each graph introduced was a probe challenging Optimist’s emerging hypotheses. Through this feedback loop, the agent evolved toward a more reliable and theoretically grounded set of conjectures.

Occasionally, the Optimist agent generated conjectures that aligned with known bounds or equations for the independence number, often appearing at the top of its conjecture lists. When these familiar relationships were recognized by the user, they were communicated to the agent, enabling Optimist to store this knowledge and exclude known results from its conjecture set going forward. This process allowed Optimist to focus on unexplored relationships. See Listing 9 for an example of updating the agent with known results.

By the conclusion of the experiment, after providing nine counterexamples, the Optimist agent had learned several key theorems, including well-known and classical results in graph theory. These learned theorems are shown in Listing 10.

The emergence of these theorems with minimal user intervention highlights Optimist’s empirical robustness and adaptability, demonstrating its potential to align autonomously with established mathematical knowledge. This adaptive capacity reflects the system’s strength in identifying both classical and novel bounds, reinforcing its value as a tool for automated reasoning in graph theory. Please see our GitHub repository⁴⁴4https://github.com/RandyRDavila/The-Optimist/tree/main for the complete experiment available as a Colab and Jupyter notebook.

The Optimist agent begins as a knowledge-based system, equipped with a foundational set of graphs and a suite of functions for computing graph invariants. From this initial setup, the agent constructs a tabular dataset, representing each graph as a unique instance and each function as a feature. This tabular structure serves as a dynamic memory, enabling Optimist to generate conjectures based on observed relationships across invariants, initially producing bounds and identities for specific graph properties.

Through interaction with a counterexample generator—referred to as the Pessimist, which can be either a human user or an autonomous agent—Optimist adapts its conjectures and knowledge base. When a counterexample is found that disproves a conjecture, the Pessimist introduces a new graph, prompting Optimist to re-evaluate its existing conjectures. This iterative feedback loop allows Optimist to refine its dataset, accumulate new graph structures, and distill empirically valid conjectures. Over time, Optimist builds a repository of both new conjectures and established theorems, increasing its capability to generate stronger, more general conjectures that remain consistent with an ever-growing dataset; effectively increasing its intelligence; see Figure 4 for an illustration.

In a future implementation where the Pessimist is also an autonomous agent, this feedback loop could operate without human intervention. The Optimist would continuously propose conjectures, while the Pessimist systematically seeks counterexamples. This interaction forms an automated cycle of discovery, where conjecture generation and counterexample search evolve concurrently, refining both conjectures and the underlying graph structures in the dataset. This setup, while unable to formally prove conjectures, would create a self-sustaining environment for empirical discovery in graph theory—a system we refer to as GraphMind.

GraphMind represents a conceptual leap toward a fully automated graph theorist. While it lacks formal proof capabilities, its ability to autonomously discover conjectures and graph structures could drive meaningful advances in graph theory. By automating the processes of hypothesis generation and empirical verification, GraphMind would serve as a powerful tool for mathematical exploration, potentially uncovering new classes of graphs, invariants, and relationships that extend beyond human intuition.