陶哲轩博客写数学问题时，通常先把对象定义清楚，再给直觉、反例和证明轮廓。把「(Luca Trevisan) Checking the Quasirandomness of Graphs and Hypergraphs」改写成可阅读的中文笔记，重点是：问题在问什么、已知到哪一步、下一步最容易走偏在哪。原站广告、分享条和导航已去掉。

问题在问什么

Notions of “quasirandomness” for graphs and hypergraphs have many applications in combinatorics and computer science. Several past posts by Terry have addressed the role of quasirandom structures in additive combinatorics. A recurring theme is that if an object (a graph, a hypergraph, a subset of integers, …) is quasirandom, then several useful properties can be immediately deduced, but, also, if an object is not quasirandom then it possesses some “structure” than can be usef

Informally, an undirected graph is quasirandom if, for every two large sets of vertices and , the number of edges between and is approximately what it would be, on average, if we had generated by picking edges uniformly at random. Quantitatively, we’ll say that a graph is -quasirandom if for every two disjoint sets of vertices and the number of edges between and differs from by at most an additive error term. This property is true with for the complete graph , and it is quite

已知结果和反例

Here are some implications of such algorithms. Consider the problem of finding a largest independent set in a given graph. (If vertices represent tasks to be performed, and an edge represents a conflict that makes it impossible to perform two tasks at the same time, a largest independent set is a largest choice of simultaneously doable tasks.) This problem is NP-hard , meaning that if there were an efficient optimization algorithm for it, there would be an algorithm that give

Now consider a random -regular graph; it is easy to find an independent set of size , and, with high probability, we can prove that the graph is -quasirandom, and hence the largest independent set has size . This means that we achieve with high probability an approximation of , and so that random graphs are not the hardest instances of the problem. Typically, in combinatorics, when random graphs are not extremal for a given problem, then finding extremal constructions is very

证明或构造的主线

The same phenomenon occurs for a number of other graph optimization problems. For example the Max Cut problem is the problem of finding a partition of the vertices of a given graph into two sets, so that a largest number of edges are “cut,” that is, have endpoints on different sides of the partition. There is a polynomial-time algorithm that achieves an approximation factor, it is NP-hard to approximate the problem better than , and there is some evidence that no approximatio

Having motivated the problem, let me briefly describe the algorithms.

阅读时建议盯住的点

First I’d like to discuss an algorithm that gives slightly worse bounds and works only on dense graphs, but is surprisingly simple: count the number of 4-cycles in the graph. This amazing result is due to Chung, Graham, Wilson and Thomason (see the introductory sections of this paper of Gowers for further references). Suppose we have a graph with vertices and edges; then a first observation is that the number of 4- cycles (that is, the number of 4-tuples of vertices such that

Note that is the average number of 4-cycles in a random graph with vertices in which each edge is included with probability . The surprising thing is that if, in a given graph, the number of 4-cycles is close to , then the graph is quasirandom. This follows from applying Cauchy-Schwarz twice, in a similar way, starting from the expression

值得单独记下的条目

• is symmetric, hence all eigenvalues are real;
• the vector is an eigenvector with eigenvalue ;
• all eigenvalues are between -d and d. Let now be the eigenvalues of , with multiplicities; as we said, .

阅读和落地时建议先做的 5 件事

1. 用自己的语言重写定义和结论，不看原文能不能说清对象是什么。
2. 找一个最小反例或边界情形，确认假设少一条会怎样。
3. 把证明拆成可独立检验的引理，每步只保留一个新想法。
4. 若涉及计算或形式化，先写可复现的小例子，再谈一般情形。
5. 记下尚未解决的缺口：缺估计、缺构造，还是缺正确的范畴。

和智能体、形式化工具怎么接

龙虾PRO做 OpenClaw 落地时，数学笔记最有用的部分往往是「可检验的步骤」：定义、反例、引理边界。智能体适合帮忙展开计算和检索，不适合代替你决定哪条假设能扔。

本文侧重全链路风控方法论。落地时请用自身业务单据做回放验证，不要把示例阈值直接当生产策略。 相关：风控体检 · 方案资源