An official website of the United States government
Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $$G = {\mathbb{F}}_2^n$$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.
more »
« less
Popular progression differences in vector spaces II
Green used an arithmetic analogue of Szemerédi's celebrated regularity lemma to prove the following strengthening of Roth's theorem in vector spaces. For every α>0, β<α3, and prime number p, there is a least positive integer n_p(α,β) such that if n≥n_p(α,β), then for every subset of 𝔽np of density at least α there is a nonzero d for which the density of three-term arithmetic progressions with common difference d is at least β. We determine for p≥19 the tower height of n_p(α,β) up to an absolute constant factor and an additive term depending only on p. In particular, if we want half the random bound (so β=α^{3}/2), then the dimension n required is a tower of twos of height Θ((log p)loglog(1/α)). It turns out that the tower height in general takes on a different form in several different regions of α and β, and different arguments are used both in the upper and lower bounds to handle these cases.
more »
« less
- Award ID(s):
- 1855635
- PAR ID:
- 10178090
- Date Published:
- Journal Name:
- Discrete analysis
- ISSN:
- 2397-3129
- Page Range / eLocation ID:
- 39 pages
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Given a Banach space X and a real number α ≥ 1, we write: (1) D ( X ) ≤ α if, for any locally finite metric space A , all finite subsets of which admit bilipschitz embeddings into X with distortions ≤ C , the space A itself admits a bilipschitz embedding into X with distortion ≤ α ⋅ C ; (2) D ( X ) = α + if, for every ϵ > 0, the condition D ( X ) ≤ α + ϵ holds, while D ( X ) ≤ α does not; (3) D ( X ) ≤ α + if D ( X ) = α + or D ( X ) ≤ α. It is known that D ( X ) is bounded by a universal constant, but the available estimates for this constant are rather large. The following results have been proved in this work: (1) D ((⊕ n =1 ∞ X n ) p ) ≤ 1 + for every nested family of finite-dimensional Banach spaces { X n } n =1 ∞ and every 1 ≤ p ≤ ∞. (2) D ((⊕ n =1 ∞ ℓ ∞ n ) p ) = 1 + for 1 < p < ∞. (3) D ( X ) ≤ 4 + for every Banach space X with no nontrivial cotype. Statement (3) is a strengthening of the Baudier–Lancien result (2008).more » « less
-
Holmsen, Kynčl and Valculescu recently conjectured that if a finite set $$X$$ with $$\ell n$$ points in $$\mathbb{R}^{d}$$ that is colored by $$m$$ different colors can be partitioned into $$n$$ subsets of $$\ell$$ points each, such that each subset contains points of at least $$d$$ different colors, then there exists such a partition of $$X$$ with the additional property that the convex hulls of the $$n$$ subsets are pairwise disjoint. We prove a continuous analogue of this conjecture, generalized so that each subset contains points of at least $$c$$ different colors, where we also allow $$c$$ to be greater than $$d$$ . Furthermore, we give lower bounds on the fraction of the points each of the subsets contains from $$c$$ different colors. For example, when $$n\geqslant 2$$ , $$d\geqslant 2$$ , $$c\geqslant d$$ with $$m\geqslant n(c-d)+d$$ are integers, and $$\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$$ are $$m$$ positive finite absolutely continuous measures on $$\mathbb{R}^{d}$$ , we prove that there exists a partition of $$\mathbb{R}^{d}$$ into $$n$$ convex pieces which equiparts the measures $$\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{d-1}$$ , and in addition every piece of the partition has positive measure with respect to at least $$c$$ of the measures $$\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$$ .more » « less
-
For a finite point set P⊂R^d, denote by diam(P) the ratio of the largest to the smallest distances between pairs of points in P. Let c_{d,α}(n) be the largest integer c such that any n-point set P⊂R^d in general position, satisfying diam(P)<αn^{1/d}, contains an c-point convex independent subset. We determine the asymptotics of c_{d,α}(n) as n→∞ by showing the existence of positive constants β=β(d,α) and γ=γ(d) such that βn^{(d−1)/(d+1)}≤c_{d,α}(n)≤γn^{(d−1)/(d+1)} for α≥2.more » « less
-
Although Bitcoin was intended to be a decentralized digital currency, in practice, mining power is quite concentrated. This fact is a persistent source of concern for the Bitcoin community. We provide an explanation using a simple model to capture miners' incentives to invest in equipment. In our model, n miners compete for a prize of fixed size. Each miner chooses an investment q_i, incurring cost c_iq_i, and then receives reward q^{\alpha}∑_j q_j^{\alpha}, for some \alpha≥1. When c_i = c+j for all i,j, and α=1, there is a unique equilibrium where all miners invest equally. However, we prove that under seemingly mild deviations from this model, equilibrium outcomes become drastically more centralized. In particular, (a) When costs are asymmetric, if miner i chooses to invest, then miner j has market share at least 1−c_j/c_i. That is, if miner j has costs that are (e.g.) 20% lower than those of miner i, then miner j must control at least 20% of the \emph{total} mining power. (b) In the presence of economies of scale (α>1), every market participant has a market share of at least 1−1/α, implying that the market features at most α/(α−1) miners in total. We discuss the implications of our results for the future design of cryptocurrencies. In particular, our work further motivates the study of protocols that minimize "orphaned" blocks, proof-of-stake protocols, and incentive compatible protocols.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
