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. 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
5. Testing k-Monotonicity

   Canonne, C; Grigorescu, E.; Guo, S; Kumar, A; Wimmer, K. (January 2017, ITCS)

   A Boolean {\em $$k$$-monotone} function defined over a finite poset domain $${\cal D}$$ alternates between the values $$0$$ and $$1$$ at most $$k$$ times on any ascending chain in $${\cal D}$$. Therefore, $$k$$-monotone functions are natural generalizations of the classical {\em monotone} functions, which are the {\em $$1$$-monotone} functions. Motivated by the recent interest in $$k$$-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $$k$$-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $$k$$-monotone (or are close to being $$k$$-monotone) from functions that are far from being $$k$$-monotone. Our results include the following: \begin{enumerate} \item We demonstrate a separation between testing $$k$$-monotonicity and testing monotonicity, on the hypercube domain $$\{0,1\}^d$$, for $$k\geq 3$$; \item We demonstrate a separation between testing and learning on $$\{0,1\}^d$$, for $$k=\omega(\log d)$$: testing $$k$$-monotonicity can be performed with $$2^{O(\sqrt d \cdot \log d\cdot \log{1/\eps})}$$ queries, while learning $$k$$-monotone functions requires $$2^{\Omega(k\cdot \sqrt d\cdot{1/\eps})}$$ queries (Blais et al. (RANDOM 2015)). \item We present a tolerant test for functions $$f\colon[n]^d\to \{0,1\}$$ with complexity independent of $$n$$, which makes progress on a problem left open by Berman et al. (STOC 2014). \end{enumerate} Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $$[n]^d$, and draw connections to distribution testing techniques. 

   more » « less