More Like this

1. Almost Everywhere Behavior of Functions According to Partition Measures

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

   Chan, William ; Jackson, Stephen ; Trang, Nam ( January 2024 , Forum of Mathematics, Sigma)

   This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals.

   The following summarizes the main results proved under suitable partition hypotheses.•

   If$\kappa $is a cardinal,$\epsilon < \kappa $,${\mathrm {cof}}(\epsilon ) = \omega $,$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the almost everywhere short length continuity property: There is a club$C \subseteq \kappa $and a$\delta < \epsilon $so that for all$f,g \in [C]^\epsilon _*$, if$f \upharpoonright \delta = g \upharpoonright \delta $and$\sup (f) = \sup (g)$, then$\Phi (f) = \Phi (g)$.

   •

   If$\kappa $is a cardinal,$\epsilon $is countable,$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$holds and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the strong almost everywhere short length continuity property: There is a club$C \subseteq \kappa $and finitely many ordinals$\delta _0, ..., \delta _k \leq \epsilon $so that for all$f,g \in [C]^\epsilon _*$, if for all$0 \leq i \leq k$,$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$, then$\Phi (f) = \Phi (g)$.

   •

   If$\kappa $satisfies$\kappa \rightarrow _* (\kappa )^\kappa _2$,$\epsilon \leq \kappa $and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the almost everywhere monotonicity property: There is a club$C \subseteq \kappa $so that for all$f,g \in [C]^\epsilon _*$, if for all$\alpha < \epsilon $,$f(\alpha ) \leq g(\alpha )$, then$\Phi (f) \leq \Phi (g)$.

   •

   Suppose dependent choice ($\mathsf {DC}$),${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$and the almost everywhere short length club uniformization principle for${\omega _1}$hold. Then every function$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$satisfies a finite continuity property with respect to closure points: Let$\mathfrak {C}_f$be the club of$\alpha < {\omega _1}$so that$\sup (f \upharpoonright \alpha ) = \alpha $. There is a club$C \subseteq {\omega _1}$and finitely many functions$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$so that for all$f \in [C]^{\omega _1}_*$, for all$g \in [C]^{\omega _1}_*$, if$\mathfrak {C}_g = \mathfrak {C}_f$and for all$i < n$,$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$, then$\Phi (g) = \Phi (f)$.

   •

   Suppose$\kappa $satisfies$\kappa \rightarrow _* (\kappa )^\epsilon _2$for all$\epsilon < \kappa $. For all$\chi < \kappa $,$[\kappa ]^{<\kappa }$does not inject into${}^\chi \mathrm {ON}$, the class of$\chi $-length sequences of ordinals, and therefore,$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$. As a consequence, under the axiom of determinacy$(\mathsf {AD})$, these two cardinality results hold when$\kappa $is one of the following weak or strong partition cardinals of determinacy:${\omega _1}$,$\omega _2$,$\boldsymbol {\delta }_n^1$(for all$1 \leq n < \omega $) and$\boldsymbol {\delta }^2_1$(assuming in addition$\mathsf {DC}_{\mathbb {R}}$).

    

   more » « less
2. New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers

   https://doi.org/10.1017/S0963548322000293  

   Cameron, Alex ; Heath, Emily ( March 2023 , Combinatorics, Probability and Computing)

   A$(p,q)$-colouring of a graph$G$is an edge-colouring of$G$which assigns at least$q$colours to each$p$-clique. The problem of determining the minimum number of colours,$f(n,p,q)$, needed to give a$(p,q)$-colouring of the complete graph$K_n$is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers$r_k(p)$. The best-known general upper bound on$f(n,p,q)$was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$p=q$have been obtained only for$p\in \{4,5\}$, each of which was proved by giving a deterministic construction which combined a$(p,p-1)$-colouring using few colours with an algebraic colouring.

   In this paper, we provide a framework for proving new upper bounds on$f(n,p,p)$in the style of these earlier constructions. We characterize all colourings of$p$-cliques with$p-1$colours which can appear in our modified version of the$(p,p-1)$-colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying$(p,p)$-colourings, which would otherwise make this problem intractable for large values of$p$. In addition, we generalize our algebraic colouring from the$p=5$setting and use this to give improved upper bounds on$f(n,6,6)$and$f(n,8,8)$.

    

   more » « less
3. Transversal Ck -factors in subgraphs of the balanced blow-up of Ck

   https://doi.org/10.1017/S0963548322000086  

   Ergemlidze, Beka ; Molla, Theodore ( November 2022 , Combinatorics, Probability and Computing)

   For a subgraph$G$of the blow-up of a graph$F$, we let$\delta ^*(G)$be the smallest minimum degree over all of the bipartite subgraphs of$G$induced by pairs of parts that correspond to edges of$F$. Johansson proved that if$G$is a spanning subgraph of the blow-up of$C_3$with parts of size$n$and$\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$, then$G$contains$n$vertex disjoint triangles, and presented the following conjecture of Häggkvist. If$G$is a spanning subgraph of the blow-up of$C_k$with parts of size$n$and$\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$, then$G$contains$n$vertex disjoint copies of$C_k$such that each$C_k$intersects each of the$k$parts exactly once. A similar conjecture was also made by Fischer and the case$k=3$was proved for large$n$by Magyar and Martin.

   In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of$G$to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically.

    

   more » « less
4. 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)

   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
5. Efficient simplicial replacement of semialgebraic sets

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

   Basu, Saugata ; Karisani, Negin ( January 2023 , Forum of Mathematics, Sigma)

   Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set$S \subset \mathbb {R}^k$by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$\Delta $, whose geometric realization,$|\Delta |$, is semialgebraically homeomorphic toS. In this paper, we consider a weaker version of this question. We prove that for any$\ell \geq 0$, there exists an algorithm which takes as input a description of a semialgebraic subset$S \subset \mathbb {R}^k$given by a quantifier-free first-order formula$\phi $in the language of the reals and produces as output a simplicial complex$\Delta $, whose geometric realization,$|\Delta |$is$\ell $-equivalent toS. The complexity of our algorithm is bounded by$(sd)^{k^{O(\ell )}}$, wheresis the number of polynomials appearing in the formula$\phi $, andda bound on their degrees. For fixed$\ell $, this bound issingly exponentialink. In particular, since$\ell $-equivalence implies that thehomotopy groupsup to dimension$\ell $of$|\Delta |$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$\ell $homotopy groups ofSto the combinatorial problem of computing the first$\ell $homotopy groups of a finite simplicial complex of size bounded by$(sd)^{k^{O(\ell )}}$.

    

   more » « less