More Like this

1. 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
2. Improved effective Łojasiewicz inequality and applications

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

   Basu, Saugata; Mohammad-Nezhad, Ali (December 2024, Forum of Mathematics, Sigma)

   Abstract Let$$\mathrm {R}$$be a real closed field. Given a closed and bounded semialgebraic set$$A \subset \mathrm {R}^n$$and semialgebraic continuous functions$$f,g:A \rightarrow \mathrm {R}$$such that$$f^{-1}(0) \subset g^{-1}(0)$$, there exist an integer$$N> 0$$and$$c \in \mathrm {R}$$such that the inequality (Łojasiewicz inequality)$$|g(x)|^N \le c \cdot |f(x)|$$holds for all$$x \in A$$. In this paper, we consider the case whenAis defined by a quantifier-free formula with atoms of the form$$P = 0, P>0, P \in \mathcal {P}$$for some finite subset of polynomials$$\mathcal {P} \subset \mathrm {R}[X_1,\ldots ,X_n]_{\leq d}$$, and the graphs of$$f,g$$are also defined by quantifier-free formulas with atoms of the form$$Q = 0, Q>0, Q \in \mathcal {Q}$$, for some finite set$$\mathcal {Q} \subset \mathrm {R}[X_1,\ldots ,X_n,Y]_{\leq d}$$. We prove that the Łojasiewicz exponent in this case is bounded by$$(8 d)^{2(n+7)}$$. Our bound depends ondandnbut is independent of the combinatorial parameters, namely the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. The previous best-known upper bound in this generality appeared inP. Solernó, Effective Łojasiewicz Inequalities in Semi-Algebraic Geometry, Applicable Algebra in Engineering, Communication and Computing (1991)and depended on the sum of degrees of the polynomials defining$$A,f,g$$and thus implicitly on the cardinalities of$$\mathcal {P}$$and$$\mathcal {Q}$$. As a consequence, we improve the current best error bounds for polynomial systems under some conditions. Finally, we prove a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We prove the existence of a common upper bound on the Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions. This improves a prior result of Chris Miller (C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic (1994)). 

   more » « less
3. 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
4. A TOPOLOGICAL APPROACH TO UNDEFINABILITY IN ALGEBRAIC EXTENSIONS OF Q

   https://doi.org/10.1017/bsl.2023.37  

   EISENTRÄGER, KIRSTEN; MILLER, RUSSELL; SPRINGER, CALEB; WESTRICK, LINDA (December 2023, The Bulletin of Symbolic Logic)

   Abstract For any subset$$Z \subseteq {\mathbb {Q}}$$, consider the set$$S_Z$$of subfields$$L\subseteq {\overline {\mathbb {Q}}}$$which contain a co-infinite subset$$C \subseteq L$$that is universally definable inLsuch that$$C \cap {\mathbb {Q}}=Z$$. Placing a natural topology on the set$${\operatorname {Sub}({\overline {\mathbb {Q}}})}$$of subfields of$${\overline {\mathbb {Q}}}$$, we show that ifZis not thin in$${\mathbb {Q}}$$, then$$S_Z$$is meager in$${\operatorname {Sub}({\overline {\mathbb {Q}}})}$$. Here,thinandmeagerboth mean “small”, in terms of arithmetic geometry and topology, respectively. For example, this implies that only a meager set of fieldsLhave the property that the ring of algebraic integers$$\mathcal {O}_L$$is universally definable inL. The main tools are Hilbert’s Irreducibility Theorem and a new normal form theorem for existential definitions. The normal form theorem, which may be of independent interest, says roughly that every$$\exists $$-definable subset of an algebraic extension of$${\mathbb Q}$$is a finite union of single points and projections of hypersurfaces defined by absolutely irreducible polynomials. 

   more » « less
5. New lower bounds for matrix multiplication and

   https://doi.org/10.1017/fmp.2023.14  

   Conner, Austin; Harper, Alicia; Landsberg, J.M. (January 2023, Forum of Mathematics, Pi)

   Abstract Let$$M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$$denote the matrix multiplication tensor (and write$$M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$$), and let$$\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$$denote the determinant polynomial considered as a tensor. For a tensorT, let$$\underline {\mathbf {R}}(T)$$denote its border rank. We (i) give the first hand-checkable algebraic proof that$$\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$$, (ii) prove$$\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$$and$$\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was$$M_{\langle 2\rangle }$$, (iii) prove$$\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$$, (iv) prove$$\underline {\mathbf {R}}(\operatorname {det}_3)=17$$, improving the previous lower bound of$$12$$, (v) prove$$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$$for all$$\mathbf {n}\geq 25$$, where previously only$$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$$was known, as well as lower bounds for$$4\leq \mathbf {n}\leq 25$$, and (vi) prove$$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$$for all$$\mathbf {n} \ge 18$$, where previously only$$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$$was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors. The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, calledborder apolaritydeveloped by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensorTand an integerr, in a finite number of steps, either outputs that there is no border rankrdecomposition forTor produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable whenThas a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory. 

   more » « less