skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on January 1, 2026

Title: Borel Vizing’s theorem for graphs of subexponential growth
We show that every Borel graph G G of subexponential growth has a Borel proper edge-coloring with Δ<#comment/> ( G ) + 1 \Delta (G) + 1 colors. We deduce this from a stronger result, namely that an n n -vertex (finite) graph G G of subexponential growth can be properly edge-colored using Δ<#comment/> ( G ) + 1 \Delta (G) + 1 colors by an O ( log ∗<#comment/> ⁡<#comment/> n ) O(\log ^\ast n) -round deterministic distributed algorithm in theLOCALmodel, where the implied constants in the O ( ⋅<#comment/> ) O(\cdot ) notation are determined by a bound on the growth rate of G G more » « less
Award ID(s):
2528522 2045412
PAR ID:
10594834
Author(s) / Creator(s):
;
Publisher / Repository:
American Mathematical Society
Date Published:
Journal Name:
Proceedings of the American Mathematical Society
Volume:
153
Issue:
787
ISSN:
0002-9939
Page Range / eLocation ID:
7 to 14
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In this paper we consider which families of finite simple groups G G have the property that for each ϵ<#comment/> > 0 \epsilon > 0 there exists N > 0 N > 0 such that, if | G | ≥<#comment/> N |G| \ge N and S , T S, T are normal subsets of G G with at least ϵ<#comment/> | G | \epsilon |G| elements each, then every non-trivial element of G G is the product of an element of S S and an element of T T . We show that this holds in a strong and effective sense for finite simple groups of Lie type of bounded rank, while it does not hold for alternating groups or groups of the form P S L n ( q ) \mathrm {PSL}_n(q) where q q is fixed and n →<#comment/> ∞<#comment/> n\to \infty . However, in the case S = T S=T and G G alternating this holds with an explicit bound on N N in terms of ϵ<#comment/> \epsilon . Related problems and applications are also discussed. In particular we show that, if w 1 , w 2 w_1, w_2 are non-trivial words, G G is a finite simple group of Lie type of bounded rank, and for g ∈<#comment/> G g \in G , P w 1 ( G ) , w 2 ( G ) ( g ) P_{w_1(G),w_2(G)}(g) denotes the probability that g 1 g 2 = g g_1g_2 = g where g i ∈<#comment/> w i ( G ) g_i \in w_i(G) are chosen uniformly and independently, then, as | G | →<#comment/> ∞<#comment/> |G| \to \infty , the distribution P w 1 ( G ) , w 2 ( G ) P_{w_1(G),w_2(G)} tends to the uniform distribution on G G with respect to the L ∞<#comment/> L^{\infty } norm. 
    more » « less
  2. Let f f be analytic on [ 0 , 1 ] [0,1] with | f ( k ) ( 1 / 2 ) | ⩽<#comment/> A α<#comment/> k k ! |f^{(k)}(1/2)|\leqslant A\alpha ^kk! for some constants A A and α<#comment/> > 2 \alpha >2 and all k ⩾<#comment/> 1 k\geqslant 1 . We show that the median estimate of μ<#comment/> = ∫<#comment/> 0 1 f ( x ) d x \mu =\int _0^1f(x)\,\mathrm {d} x under random linear scrambling with n = 2 m n=2^m points converges at the rate O ( n −<#comment/> c log ⁡<#comment/> ( n ) ) O(n^{-c\log (n)}) for any c > 3 log ⁡<#comment/> ( 2 ) / π<#comment/> 2 ≈<#comment/> 0.21 c> 3\log (2)/\pi ^2\approx 0.21 . We also get a super-polynomial convergence rate for the sample median of 2 k −<#comment/> 1 2k-1 random linearly scrambled estimates, when k / m k/m is bounded away from zero. When f f has a p p ’th derivative that satisfies a λ<#comment/> \lambda -Hölder condition then the median of means has error O ( n −<#comment/> ( p + λ<#comment/> ) + ϵ<#comment/> ) O( n^{-(p+\lambda )+\epsilon }) for any ϵ<#comment/> > 0 \epsilon >0 , if k →<#comment/> ∞<#comment/> k\to \infty as m →<#comment/> ∞<#comment/> m\to \infty . The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number. 
    more » « less
  3. We investigate a conjecture due to Haefliger and Thurston in the context of foliated manifold bundles. In this context, Haefliger-Thurston’s conjecture predicts that every M M -bundle over a manifold B B where dim ⁡<#comment/> ( B ) ≤<#comment/> dim ⁡<#comment/> ( M ) \operatorname {dim}(B)\leq \operatorname {dim}(M) is cobordant to a flat M M -bundle. In particular, we study the bordism class of flat M M -bundles over low dimensional manifolds, comparing a finite dimensional Lie group G G with D i f f 0 ( G ) \mathrm {Diff}_0(G)
    more » « less
  4. In this paper, we consider higher regularity of a weak solution ( u , p ) (\mathbf {u},p) to stationary Stokes systems with variable coefficients. Under the assumptions that coefficients and data are piecewise C s , δ<#comment/> C^{s,\delta } in a bounded domain consisting of a finite number of subdomains with interfacial boundaries in C s + 1 , μ<#comment/> C^{s+1,\mu } , where s s is a positive integer, δ<#comment/> ∈<#comment/> ( 0 , 1 ) \delta \in (0,1) , and μ<#comment/> ∈<#comment/> ( 0 , 1 ] \mu \in (0,1] , we show that D u D\mathbf {u} and p p are piecewise C s , δ<#comment/> μ<#comment/> C^{s,\delta _{\mu }} , where δ<#comment/> μ<#comment/> = min { 1 2 , μ<#comment/> , δ<#comment/> } \delta _{\mu }=\min \big \{\frac {1}{2},\mu ,\delta \big \} . Our result is new even in the 2D case with piecewise constant coefficients. 
    more » « less
  5. We study regularity of solutions u u to ∂<#comment/> ¯<#comment/> u = f \overline \partial u=f on a relatively compact C 2 C^2 domain D D in a complex manifold of dimension n n , where f f is a ( 0 , q ) (0,q) form. Assume that there are either ( q + 1 ) (q+1) negative or ( n −<#comment/> q ) (n-q) positive Levi eigenvalues at each point of boundary ∂<#comment/> D \partial D . Under the necessary condition that a locally L 2 L^2 solution exists on the domain, we show the existence of the solutions on the closure of the domain that gain 1 / 2 1/2 derivative when q = 1 q=1 and f f is in the Hölder–Zygmund space Λ<#comment/> r ( D ) \Lambda ^r( D) with r > 1 r>1 . For q > 1 q>1 , the same regularity for the solutions is achieved when ∂<#comment/> D \partial D is either sufficiently smooth or of ( n −<#comment/> q ) (n-q) positive Levi eigenvalues everywhere on ∂<#comment/> D \partial D
    more » « less