Fajtlowicz's Graffiti
=====================

The *Graffiti* program, developed by Siemion Fajtlowicz in the 1980s, was one of the first systems to generate novel mathematical conjectures. It proposed inequalities between graph invariants — such as independence number, residue, radius, and domination number — and led to the discovery and eventual proofs of dozens of new theorems.

Many of these conjectures were generated by comparing two quantities across a dataset of graphs and recording whether a consistent inequality appeared. The results were then filtered using human insight or light postprocessing.

TxGraffiti generalizes and formalizes this idea using **conjecture generators** and **heuristics** — most notably, the **Dalmatian heuristic**:

**The Dalmatian Heuristic**:
- **Truth Test**: The inequality must hold for all known graphs.
- **Significance Test**: It must give a strictly better bound for at least one graph than previously known inequalities.
- The name “Dalmatian” comes from the idea that each conjecture should "touch" a different spot in the data, like spots on a Dalmatian.

The following example simulates the behavior of the original *Graffiti* program.

Minimal Simulation of Graffiti
------------------------------

We use the `ConjecturePlayground` class to propose inequalities between graph invariants using the `ratios` generator and `dalmatian` heuristic.

.. code-block:: python

    from txgraffiti.playground    import ConjecturePlayground
    from txgraffiti.generators    import ratios
    from txgraffiti.heuristics    import dalmatian
    from txgraffiti.example_data  import graph_data   # bundled toy graph dataset

    graffiti = ConjecturePlayground(
        graph_data,
        object_symbol='G',
        base='connected',
    )

    graffiti.discover(
        methods    = [ratios],
        features   = [graffiti.residue, graffiti.radius],
        target     = 'independence_number',
        heuristics = [dalmatian],
    )

    for idx, conj in enumerate(graffiti.conjectures[:10], start=1):
        formula = graffiti.forall(conj)
        print(f"Conjecture {idx}. {formula}\n")

Output:

.. code-block:: text

    Conjecture 1. ∀ G: (connected) → (independence_number ≥ residue)

    Conjecture 2. ∀ G: (connected) → (independence_number ≤ (2 * residue))

    Conjecture 3. ∀ G: (connected) → (independence_number ≥ radius)

    Conjecture 4. ∀ G: (connected) → (independence_number ≤ (13 * radius))

Historical Note
---------------

- **Conjecture 1** and **Conjecture 3** are two of the most well known conjectures of Graffiti

These results demonstrate how TxGraffiti not only generalizes Graffiti’s approach but can also *rediscover* known results — a powerful indicator of its mathematical relevance.

Heuristic Philosophy
--------------------

The **Dalmatian heuristic** is a modern formalization of what Graffiti did informally:

- It retains only conjectures that are true across all known data
- It checks for *significance* — the conjecture must be sharp (tight) on at least one example
- The result is a filtered set of inequalities that tend to be *mathematically meaningful*