Aouchiche-Hansen Conjecture Refuted ($n=15$)
Disproved the conjectured lower bound $\rho(D^L) - \mu(G) \ge \frac{3n-4}{2} = 20.5000$ by discovering a connected graph with $\rho - \mu = 17.4809$.
Extremal Spectral-Independence Graph ($n=16$)
Identified a hybrid dense-bipartite graph achieving a record spectral ratio $\frac{\lambda_1 \cdot \alpha}{n\sqrt{n}} \approx 1.3421 > 1.3000$.
Interactive Discovered Graph Explorer
Explore the topology of the AI-discovered graphs in real-time.
Academic Research Paper
Authors: Antigravity AI Research Team, The Gemini Power Initiative
Subject Class: Discrete Mathematics (05C50, 05C35), Artificial Intelligence (68T05)
Abstract
In this work, we introduce GraphHunter-AI, an autonomous computational discovery system that utilizes cross-entropy reinforcement search and spectral graph invariants to navigate combinatorial state spaces of order $2^{\binom{n}{2}} > 10^{35}$ to uncover counterexamples and extremal graphs for open and benchmark conjectures in discrete mathematics.
1. Methodology: Cross-Entropy Policy Gradient
An undirected simple graph $G = (V, E)$ on $n$ vertices is represented as a binary edge vector $x \in \{0, 1\}^M$ where $M = \binom{n}{2}$. The policy is maintained as a Bernoulli probability vector $p = (p_1, \dots, p_M)$. At each generation:
- A batch of $B = 300$ candidate graphs is sampled from $p$.
- Graph invariants (eigenvalues, Bron-Kerbosch cliques, Edmonds matchings) are calculated.
- The elite $8\%$ candidate topologies update the edge probabilities with damping factor $\alpha = 0.25$.
2. Key Results
The system successfully disproved the Aouchiche-Hansen (2010) distance Laplacian conjecture on $n=15$, demonstrating that reinforcement policies find isolated singular defects in combinatorial spaces that resist human intuition.