RamseyGadgets：LLM 的图构建数据集

构造特殊图是图论和计算机科学中的一项重要任务。许多流行的图构造都是对相关图和人类聪明才智进行综合探索的结果。鉴于生成式人工智能在数学中的使用不断增加，测试 LLM 是否能够利用其推理能力构建具有指定属性的图是很自然的。不幸的是，许多自然图构造问题，例如寻找极值拉姆齐好图（即，避免特定的单色子图），已在文献中进行了广泛探讨，这使得很难确定构造是否是 LLM 推理能力的产物或其从训练数据中收集的结果。在这项工作中，我们引入了 \textbf{RamseyGadgets}，这是一个包含 70 个未充分探索的图构造问题的新颖数据集，需要找到具有特殊属性（例如，包含具有固定颜色的边）的 Ramsey 良好图。这些问题具有合理大小的解决方案（最多 10 个顶点），可以通过 SAT 求解器进行验证，使其适合自动评估。我们的数据集很容易扩展，因为人们可以简单地改变要避免的单色子图以获得一组新的问题。我们评估了五个开源 LLM 在我们的数据集上的性能并报告结果。我们的研究结果表明，LLM 在我们数据集中的硬层问题上仅实现了 37.70% 的准确率，而 Gemma-4-31B 在这五个问题中实现了最高的性能。我们还展示了我们的数据集如何让我们确定什么样的提示可以帮助 LLM 在这项任务中表现得更好。