More Like this

1. Short Proof of the Asymptotic Confirmation of the Faudree-Lehel Conjecture

   https://doi.org/10.37236/11413  

   Przybyło, Jakub; Wei, Fan (October 2023, The Electronic Journal of Combinatorics)

   Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough. 

   more » « less
2. Additive Energies on Discrete Cubes

   de Dios Pont, Jaume; Greenfeld, Rachel; Ivanisvili, Paata; Madrid, Jose (September 2023, Discrete analysis)

   Gowers, Tim (Ed.)

   We prove that for $$d\geq 0$$ and $$k\geq 2$$, for any subset $$A$$ of a discrete cube $$\{0,1\}^d$$, the $k-$higher energy of $$A$$ (i.e., the number of $2k-$tuples $$(a_1,a_2,\dots,a_{2k})$$ in $$A^{2k}$$ with $$a_1-a_2=a_3-a_4=\dots=a_{2k-1}-a_{2k}$$) is at most $$|A|^{\log_{2}(2^k+2)}$$, and $$\log_{2}(2^k+2)$$ is the best possible exponent. We also show that if $$d\geq 0$$ and $$2\leq k\leq 10$$, for any subset $$A$$ of a discrete cube $$\{0,1\}^d$$, the $k-$additive energy of $$A$$ (i.e., the number of $2k-$tuples $$(a_1,a_2,\dots,a_{2k})$$ in $$A^{2k}$$ with $$a_1+a_2+\dots+a_k=a_{k+1}+a_{k+2}+\dots+a_{2k}$$) is at most $$|A|^{\log_2{ \binom{2k}{k}}}$$, and $$\log_2{ \binom{2k}{k}}$$ is the best possible exponent. We discuss the analogous problems for the sets $$\{0,1,\dots,n\}^d$$ for $$n\geq2$$. 

   more » « less
3. Universality for 1d Random Band Matrices: Sigma-Model Approximation

   https://doi.org/10.1007/s10955-018-1969-1  

   Shcherbina, Mariya; Shcherbina, Tatyana (January 2018, Journal of Statistical Physics)

   The paper continues the development of the rigorous supersymmetric transfer matrix approach to the random band matrices started in (J Stat Phys 164:1233–1260, 2016; Commun Math Phys 351:1009–1044, 2017). We consider random Hermitian block band matrices consisting of $$W\times W$$ random Gaussian blocks (parametrized by $$j,k \in\Lambda=[1,n]^d\cap \mathbb{Z}^d$$) with a fixed entry's variance $$J_{jk}=\delta_{j,k}W^{-1}+\beta\Delta_{j,k}W^{-2}$$, $$\beta>0$$ in each block. Taking the limit $$W\to\infty$$ with fixed $$n$$ and $$\beta$$, we derive the sigma-model approximation of the second correlation function similar to Efetov's one. Then, considering the limit $$\beta, n\to\infty$$, we prove that in the dimension $d=1$ the behaviour of the sigma-model approximation in the bulk of the spectrum, as $$\beta\gg n$$, is determined by the classical Wigner -- Dyson statistics. 

   more » « less
4. Computable error bounds for quasi-Monte Carlo using points with non-negative local discrepancy

   https://doi.org/10.1093/imaiai/iaae021  

   Gnewuch, Michael; Kritzer, Peter; Owen, Art_B; Pan, Zexin (August 2024, Information and Inference: A Journal of the IMA)

   Abstract Let $$f:[0,1]^{d}\to{\mathbb{R}}$$ be a completely monotone integrand as defined by Aistleitner and Dick (2015, Acta Arithmetica, 167, 143–171) and let points $$\boldsymbol{x}_{0},\dots ,\boldsymbol{x}_{n-1}\in [0,1]^{d}$$ have a non-negative local discrepancy (NNLD) everywhere in $$[0,1]^{d}$$. We show how to use these properties to get a non-asymptotic and computable upper bound for the integral of $$f$$ over $$[0,1]^{d}$$. An analogous non-positive local discrepancy property provides a computable lower bound. It has been known since Gabai (1967, Illinois J. Math., 11, 1–12) that the two-dimensional Hammersley points in any base $$b\geqslant 2$$ have NNLD. Using the probabilistic notion of associated random variables, we generalize Gabai’s finding to digital nets in any base $$b\geqslant 2$$ and any dimension $$d\geqslant 1$$ when the generator matrices are permutation matrices. We show that permutation matrices cannot attain the best values of the digital net quality parameter when $$d\geqslant 3$$. As a consequence the computable absolutely sure bounds we provide come with less accurate estimates than the usual digital net estimates do in high dimensions. We are also able to construct high-dimensional rank one lattice rules that are NNLD. We show that those lattices do not have good discrepancy properties: any lattice rule with the NNLD property in dimension $$d\geqslant 2$$ either fails to be projection regular or has all its points on the main diagonal. Complete monotonicity is a very strict requirement that for some integrands can be mitigated via a control variate. 

   more » « less
5. On the Strict Majorant Property in Arbitrary Dimensions

   https://doi.org/10.1093/qmath/haac021  

   Gressman, P T; Guo, S; Pierce, L B; Roos, J; Yung, P -L (July 2022, The Quarterly Journal of Mathematics)

   Abstract In this work we study d-dimensional majorant properties. We prove that a set of frequencies in $$\mathbb{Z}^d$$ satisfies the strict majorant property on $L^p([0,1]^d)$ for all p > 0 if and only if the set is affinely independent. We further construct three types of violations of the strict majorant property. Any set of at least d + 2 frequencies in $$\mathbb{Z}^d$$ violates the strict majorant property on $L^p([0,1]^d)$ for an open interval of $$p \not\in 2\mathbb{N}$$ of length 2. Any infinite set of frequencies in $$\mathbb{Z}^d$$ violates the strict majorant property on $L^p([0,1]^d)$ for an infinite sequence of open intervals of $$p \not\in 2\mathbb{N}$$ of length 2. Finally, given any p > 0 with $$p \not\in 2\mathbb{N}$$, we exhibit a set of d + 2 frequencies on the moment curve in $$\mathbb{R}^d$$ that violate the strict majorant property on $L^p([0,1]^d).$ 

   more » « less