论文标题
几个4循环的图形的规则方法
The regularity method for graphs with few 4-cycles
论文作者
论文摘要
我们开发了一种稀疏的图表规则方法，该方法适用于几个4个循环的图，包括在此类图中的5个循环的新计数和去除引理。一些应用程序包括： *通过删除$ o（n^{3/2}）$ edges，每个$ n $ vertex图都可以使没有5个周期的图形不含三角形。 *对于$ r \ geq 3 $，每个$ n $ -vertex $ r $ r $ - 带有$ 5 $ $ o（n^{3/2}）$ edge的graph。 * $ [n] $的每个子集都没有方程式的非平地解决方案$ x_1 + x_2 + 2x_3 = x_4 + 3x_5 $具有尺寸$ o（\ sqrt {n}）$。
We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include: * Every $n$-vertex graph with no 5-cycle can be made triangle-free by deleting $o(n^{3/2})$ edges. * For $r \geq 3$, every $n$-vertex $r$-graph with girth greater than $5$ has $o(n^{3/2})$ edges. * Every subset of $[n]$ without a nontrivial solution to the equation $x_1 + x_2 + 2x_3 = x_4 + 3x_5$ has size $o(\sqrt{n})$.
