More Like this

1. Multi-linear forms, graphs, and $L^p$-improving measures in $${\Bbb F}_q^d$$

   https://doi.org/10.4153/S0008414X2300086X  

   Bhowmik, Pablo; Iosevich, Alex; Koh, Doowon; Pham, Thang (February 2025, Canadian journal of mathematics)

   Abstract The purpose of this paper is to introduce and study the following graph-theoretic paradigm. Let$$ \begin{align*}T_Kf(x)=\int K(x,y) f(y) d\mu(y),\end{align*} $$where$$f: X \to {\Bbb R}$$,Xa set, finite or infinite, andKand$$\mu $$denote a suitable kernel and a measure, respectively. Given a connected ordered graphGonnvertices, consider the multi-linear form$$ \begin{align*}\Lambda_G(f_1,f_2, \dots, f_n)=\int_{x^1, \dots, x^n \in X} \ \prod_{(i,j) \in {\mathcal E}(G)} K(x^i,x^j) \prod_{l=1}^n f_l(x^l) d\mu(x^l),\end{align*} $$where$${\mathcal E}(G)$$is the edge set ofG. Define$$\Lambda _G(p_1, \ldots , p_n)$$as the smallest constant$$C>0$$such that the inequality(0.1)$$ \begin{align} \Lambda_G(f_1, \dots, f_n) \leq C \prod_{i=1}^n {||f_i||}_{L^{p_i}(X, \mu)} \end{align} $$holds for all nonnegative real-valued functions$$f_i$$,$$1\le i\le n$$, onX. The basic question is, how does the structure ofGand the mapping properties of the operator$$T_K$$influence the sharp exponents in (0.1). In this paper, this question is investigated mainly in the case$$X={\Bbb F}_q^d$$, thed-dimensional vector space over the field withqelements,$$K(x^i,x^j)$$is the indicator function of the sphere evaluated at$$x^i-x^j$$, and connected graphsGwith at most four vertices. 

   more » « less
2. Large monochromatic components in expansive hypergraphs

   https://doi.org/10.1017/S096354832400004X  

   Bal, Deepak; DeBiasio, Louis (March 2024, Combinatorics, Probability and Computing)

   Abstract A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary$$r$$-colouring of the complete$$k$$-uniform hypergraph$$K_n^k$$when$$k\geq 2$$and$$k\in \{r-1,r\}$$. We prove a result which says that if one replaces$$K_n^k$$in Gyárfás’ theorem by any ‘expansive’$$k$$-uniform hypergraph on$$n$$vertices (that is, a$$k$$-uniform hypergraph$$G$$on$$n$$vertices in which$$e(V_1, \ldots, V_k)\gt 0$$for all disjoint sets$$V_1, \ldots, V_k\subseteq V(G)$$with$$|V_i|\gt \alpha$$for all$$i\in [k]$$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on$$r$$and$$\alpha$$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary$$r$$-partite$$r$$-uniform hypergraph$$H$$with$$n$$edges in which every set of$$k$$edges has a common intersection. In this language, our result says that if one replaces the condition that every set of$$k$$edges has a common intersection with the condition that for every collection of$$k$$disjoint sets$$E_1, \ldots, E_k\subseteq E(H)$$with$$|E_i|\gt \alpha$$, there exists$$(e_1, \ldots, e_k)\in E_1\times \cdots \times E_k$$such that$$e_1\cap \cdots \cap e_k\neq \emptyset$$, then the smallest possible maximum degree of$$H$$is essentially the same (within a small error term depending on$$r$$and$$\alpha$$). We prove our results in this dual setting. 

   more » « less
3. On approximability of satisfiable $$\boldsymbol {k}$$-CSPs: II

   https://doi.org/10.1017/S0963548325100114  

   Bhangale, Amey; Khot, Subhash; Minzer, Dor (November 2025, Combinatorics, Probability and Computing)

   Abstract Let$$\Sigma$$be an alphabet and$$\mu$$be a distribution on$$\Sigma ^k$$for some$$k \geqslant 2$$. Let$$\alpha \gt 0$$be the minimum probability of a tuple in the support of$$\mu$$(denoted$$\mathsf{supp}(\mu )$$). We treat the parameters$$\Sigma , k, \mu , \alpha$$as fixed and constant. We say that the distribution$$\mu$$has a linear embedding if there exist an Abelian group$$G$$(with the identity element$$0_G$$) and mappings$$\sigma _i : \Sigma \rightarrow G$$,$$1 \leqslant i \leqslant k$$, such that at least one of the mappings is non-constant and for every$$(a_1, a_2, \ldots , a_k)\in \mathsf{supp}(\mu )$$,$$\sum _{i=1}^k \sigma _i(a_i) = 0_G$$. In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let$$f_i: \Sigma ^n\rightarrow [\!-1,1]$$be bounded functions, such that at least one of the functions$$f_i$$essentially has degree at least$$d$$, meaning that the Fourier mass of$$f_i$$on terms of degree less than$$d$$is at most$$\delta$$. If$$\mu$$has no linear embedding (over any Abelian group), then is it necessarily the case that\begin{equation*}\left | \mathop {\mathbb{E}}_{({\textbf {x}}_1, {\textbf {x}}_2, \ldots , {\textbf {x}}_k)\sim \mu ^{\otimes n}}[f_1({\textbf {x}}_1)f_2({\textbf {x}}_2)\cdots f_k({\textbf {x}}_k)] \right | = o_{d, \delta }(1),\end{equation*}where the right hand side$$\to 0$$as the degree$$d \to \infty$$and$$\delta \to 0$$? In this paper, we answer this analytical question fully and in the affirmative for$$k=3$$. We also show the following two applications of the result.1.The first application is related to hardness of approximation. Using the reduction from [5], we show that for every$$3$$-ary predicate$$P:\Sigma ^3 \to \{0,1\}$$such that$$P$$has no linear embedding, anSDP (semi-definite programming) integrality gap instanceof a$$P$$-Constraint Satisfaction Problem (CSP) instance with gap$$(1,s)$$can be translated into a dictatorship test with completeness$$1$$and soundness$$s+o(1)$$, under certain additional conditions on the instance.2.The second application is related to additive combinatorics. We show that if the distribution$$\mu$$on$$\Sigma ^3$$has no linear embedding, marginals of$$\mu$$are uniform on$$\Sigma$$, and$$(a,a,a)\in \texttt{supp}(\mu )$$for every$$a\in \Sigma$$, then every large enough subset of$$\Sigma ^n$$contains a triple$$({\textbf {x}}_1, {\textbf {x}}_2,{\textbf {x}}_3)$$from$$\mu ^{\otimes n}$$(and in fact a significant density of such triples). 

   more » « less
4. Bipartite-ness under smooth conditions

   https://doi.org/10.1017/S0963548323000019  

   Jiang, Tao; Longbrake, Sean; Ma, Jie (February 2023, Combinatorics, Probability and Computing)

   Abstract Given a family$$\mathcal{F}$$of bipartite graphs, theZarankiewicz number$$z(m,n,\mathcal{F})$$is the maximum number of edges in an$$m$$by$$n$$bipartite graph$$G$$that does not contain any member of$$\mathcal{F}$$as a subgraph (such$$G$$is called$$\mathcal{F}$$-free). For$$1\leq \beta \lt \alpha \lt 2$$, a family$$\mathcal{F}$$of bipartite graphs is$$(\alpha,\beta )$$-smoothif for some$$\rho \gt 0$$and every$$m\leq n$$,$$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any$$(\alpha,\beta )$$-smooth family$$\mathcal{F}$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$$is bipartite. In this paper, we strengthen their result by showing that for every real$$\delta \gt 0$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\delta n^{\alpha -1}$$is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$$\mathcal{F}$$consisting of the single graph$$K_{s,t}$$when$$t\gg s$$. We also prove an analogous result for$$C_{2\ell }$$-free graphs for every$$\ell \geq 2$$, which complements a result of Keevash, Sudakov and Verstraëte. 

   more » « less
5. Bohr sets in sumsets II: countable abelian groups

   https://doi.org/10.1017/fms.2023.49  

   Griesmer, John T.; Le, Anh N.; Lê, Thái Hoàng (July 2023, Forum of Mathematics, Sigma)

   Abstract We prove three results concerning the existence of Bohr sets in threefold sumsets. More precisely, lettingGbe a countable discrete abelian group and$$\phi _1, \phi _2, \phi _3: G \to G$$be commuting endomorphisms whose images have finite indices, we show that(1)If$$A \subset G$$has positive upper Banach density and$$\phi _1 + \phi _2 + \phi _3 = 0$$, then$$\phi _1(A) + \phi _2(A) + \phi _3(A)$$contains a Bohr set. This generalizes a theorem of Bergelson and Ruzsa in$$\mathbb {Z}$$and a recent result of the first author.(2)For any partition$$G = \bigcup _{i=1}^r A_i$$, there exists an$$i \in \{1, \ldots , r\}$$such that$$\phi _1(A_i) + \phi _2(A_i) - \phi _2(A_i)$$contains a Bohr set. This generalizes a result of the second and third authors from$$\mathbb {Z}$$to countable abelian groups.(3)If$$B, C \subset G$$have positive upper Banach density and$$G = \bigcup _{i=1}^r A_i$$is a partition,$$B + C + A_i$$contains a Bohr set for some$$i \in \{1, \ldots , r\}$$. This is a strengthening of a theorem of Bergelson, Furstenberg and Weiss. All results are quantitative in the sense that the radius and rank of the Bohr set obtained depends only on the indices$$[G:\phi _j(G)]$$, the upper Banach density ofA(in (1)), or the number of sets in the given partition (in (2) and (3)). 

   more » « less