The Lovasz gap, i.e. theta-alpha, can be arbitrary large.
Prf:
Let G be a cycle with N vertices.
Fuse a pentagon on each of the vertices of G.
Then theta(G)-alpha(G)=N(sqrt(5)-2), which can be arbitrary large as N->infinity.

The gap is bounded by 5 if G is a complete graph, as shown:

Using a complete graph is bound to fail, as what the gap really depends on is the density.

先想想怎样才能提出正确且逻辑上独立的猜想吧，不需要关注所谓的“价值论”*。
所谓“逻辑上独立”，指没有作为定理证明过，也没有作为猜想提出过，前提不要莫名其妙的强，结论也不要莫名其妙的弱。
比如这四个猜想：
这个作为猜想提出过：（猜想：所有非Petersen的强正则图都有哈密顿圈）
(((is_locally_bipartite)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
这个前提太强：
(((is_independence_irreducible)->(is_line_graph))&(is_strongly_regular))->(is_hamiltonian)
这个作为定理证明过：
(((is_line_graph)&(is_complement_of_chordal))&(has_radius_equal_diameter))->(is_hamiltonian)
这个结论太弱：
alpha <= (average_distance)^(degree_sum) （事实上不等式右端几乎总是大于图的点数）

错误的猜想，如果仅仅在trivial的情况错误，其价值也比上面几个猜想（尽管有两个正确的）好很多。
也就是说，我们似乎在某种“几何”里思考，其中trivial的情况的测度是0.

"价值论"的提法估计是从arxiv 1801.01814里得到的：
Consider for example the conjecturing program of Hao Wang.Wang was an automated mathematical discovery pioneer while he wasat IBM in the late 1950s and the developer of the first conjecturingprogram. He wanted his program to produce “interesting” mathematicalstatements—but he didn’t factor in any mathematical goal.He reported: “The number of theorems printed out after running themachine for a few hours is so formidable that the writer has not evenattempted to analyze the mass of data obtained.” If some of these statements were mathematical advances Wang didn’t know it. Ourhuman goals are central to the success and (human) evaluation of ourmathematical progress.
不过我认为最重要的问题是——猜想太多了，没法检查。
如果需要把猜想的质量提上，猜想的数目必然减少，这时就可以靠人类检查。
另外，“Our human goals are central to the success and (human) evaluation of our mathematical progress”，这句话说得不错，但是human goals是极其多元化的，不排除计算机猜想为human goals增添新的元素。
就是说，计算机没有必要紧跟人类价值，其自身就可以创造一种新的价值。

我们做的不是“拟人智能”，没有必要继承人类的任何特点（语言除外）。
如果说价值根植于生活，那么作为一个生活形式与人不同的计算机，其价值也未必和人一样。
任何根植于生活的都可以由此照猫画虎。
当然语言除外——否则就没法和程序交流了。

*不是说这种程序不需要“价值论”，而是可以用一个比人类价值论简单n倍的deficient axiology:
一事物就是自身价值的显现。
有些命题能够作为猜想提出，有些则没有，是因为那些被提出的命题能够显现自身的价值。
这一价值还能够渗透，也就是说，相互联系的命题，其价值也有相互联系。最简单的例子就是条件弱的命题价值高。

其实这两个猜想还是很不错的，只不过错了
((is_heliotropic_plant)&(is_regular))->(is_hamiltonian)
((is_heliotropic_plant)&(is_two_connected))->(is_hamiltonian)
觉得这几个有点神经病
alpha <= diameter^(max_degree-1)
independence_number(x) >= minimum(diameter(x), lovasz_theta(x))
independence_number(x) >= min(card_positive_eigenvalues(x), 2*card_zero_eigenvalues(x))

说真的，现在能找到的“正确且逻辑上独立的猜想”只有三个：
1.γ<m/2-h (Automated Conjecturing Approach for Benzenoids)，已证，正在写论文
2.Bipartite semisymmetric graphs are hamiltonian，估计没啥希望证出来
3.Bipartite distance-regular graphs are hamiltonian，估计可以对足够大的图证明，对小图一一列举。我觉得我目前只能掌握Bipartite distance-transitive graphs的情况。（估计Bipartite DTG可以完全分类，不过这个结果也很不错）

有种工程方法：把猜想按照其本身的规律画成一张图（总之，利用数据可视化方法），比一条一条地列出来好。人们更会花时间关注这些猜想。
经文：跟人类交流未必需要继承人类的价值论。

各种不同猜想（甚至是句子）之间存在关系，比如加强，置换其中一个词，∀x∃y -> ∃x∀y ，等等。
句子之间的关系如何反映世界中的关系，是我们要研究的。

有些东西天生就适合被枪毙，比如完全图。
甚至有些东西天生就适合和完全图一起被枪毙，比如奇圈。

之前好几楼都在讨论价值论。
我觉得还可以从另一个方向考虑：行为算子。（就是各种优化算法里的那种）
就是说，程序的行动并不是根据“价值最大化”行动，而是由一套给定的行为算子行动。这套算子的存在和价值并无联系。
使用行为算子，在实际编程时会比较简单。
行为算子还可以生成一些并不是命题的东西，比如“不要考虑含有vacuous truth子句的命题”，或者“优先考虑完全图”，这在价值论世界里是难以想象的。