An official website of the United States government
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Abstract We provide a deterministic algorithm that finds, in ɛ - O (1) n 2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ - O (1) many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ɛn v(H) , in time ɛ - O H (1) n 2 .more » « less
-
Let G be an abelian group of bounded exponent and A⊆G. We show that if the collection of translates of A has VC dimension at most d, then for every ϵ>0 there is a subgroup H of G of index at most ϵ^{−d−o(1)} such that one can add or delete at most ϵ|G| elements to/from A to make it a union of H-cosets. We also establish a removal lemma with polynomial bounds, with applications to property testing, for induced bipartite patterns in a finite abelian group with bounded exponent.more » « less
-
null (Ed.)Abstract Let Xk denote the number of k-term arithmetic progressions in a random subset of $$\mathbb{Z}/N\mathbb{Z}$$ or $$\{1, \dots , N\}$$ where every element is included independently with probability p. We determine the asymptotics of $$\log \mathbb{P}\big (X_{k} \ge \big (1+\delta \big ) \mathbb{E} X_{k}\big )$$ (also known as the large deviation rate) where p → 0 with $$p \ge N^{-c_{k}}$$ for some constant ck > 0, which answers a question of Chatterjee and Dembo. The proofs rely on the recent nonlinear large deviation principle of Eldan, which improved on earlier results of Chatterjee and Dembo. Our results complement those of Warnke, who used completely different methods to estimate, for the full range of p, the large deviation rate up to a constant factor.more » « less
