Coloring triangle‐free graphs with local list sizes

We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow‐up work of Bernshteyn) on the (list) chromatic number of triangle‐free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring. Our proof of the second illustrates the use of the hard‐core model to prove a Johansson‐type result, which may be of independent interest.     

A Local Expansion Theorem for the Löwner Equation

If W(z) is a power series with complex coefficients which represents an injective function bounded by one in the unit disk and which vanishes at the origin then a Grunsky space $\mathcal{G}(W)$ exists. It is contained contractively in the Dirichlet space for the unit disk. In this paper an admissible family of weighted Dirichlet spaces is used as in the proof of Bieberbach conjecture to construct a Local Grunsky space. An expansion theorem is presented for such a Local Grunsky space. The proof relies on the reproducing kernel function for coefficients of powers of z and Löwner differential equation.     

Maximal regularity, the local inverse function theorem, and local well-posedness for the curve shortening flow

Local well-posedness of the curve shortening flow, that is, local existence, uniqueness and smooth dependence of solutions on initial data, is proved by applying the Local Inverse Function Theorem and L ²-maximal regularity results for linear parabolic equations. The application of the Local Inverse Function Theorem leads to a particularly short proof which gives in addition the space-time regularity of the solutions. The method may be applied to general nonlinear evolution equations, but is presented in the special situation only.     

A note on a Brooks' type theorem for DP-coloring

Dvořák and Postle introduced DP-coloring of simple graphs as a generalization of list-coloring. They proved a Brooks' type theorem for DP-coloring; and Bernshteyn, Kostochka, and Pron extended it to DP-coloring of multigraphs. However, detailed structure, when a multigraph does not admit DP-coloring, was not specified. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs.     

The stable manifold theorem for non-linear stochastic systems with memory: II. The local stable manifold theorem

We state and prove a Local Stable Manifold Theorem (Theorem 4.1) for non-linear stochastic differential systems with finite memory (viz. stochastic functional differential equations (sfde's)). We introduce the notion of hyperbolicity for stationary trajectories of sfde's. We then establish the existence of smooth stable and unstable manifolds in a neighborhood of a hyperbolic stationary trajectory. The stable and unstable manifolds are stationary and asymptotically invariant under the stochastic semiflow. The proof uses infinite-dimensional multiplicative ergodic theory techniques developed by D. Ruelle, together with interpolation arguments.     

Weakly hyperbolic involutions

Pfister’s Local–Global Principle states that a quadratic form over a (formally) real field is weakly hyperbolic (i.e. represents a torsion element in the Witt ring) if and only if its total signature is zero. This result extends naturally to the setting of central simple algebras with involution. The present article provides a new proof of this result and extends it to the case of signatures at preorderings. Furthermore the quantitative relation between nilpotence and torsion is explored for quadratic forms as well as for central simple algebras with involution.     

Local discrepancies in the problem of fractional parts distribution of a linear function

In this paper we consider a problem of distribution of fractional parts of the sequence obtained as multiples of some irrational number with bounded partial quotients of its continued fraction expansion. Local discrepancies are the remainder terms of asymptotic formulas for the number of points of the sequence lying in given intervals. Earlier only intervals with bounded and logarithmic local discrepancies were known. We prove that there exists an infinite set of intervals with arbitrary small growth rate of local discrepancies. The proof is based on the connection of considered problem with some of those from Diophantine approximations.     

The Local Cut Lemma

The Lovász Local Lemma is a very powerful tool in probabilistic combinatorics, that is often used to prove existence of combinatorial objects satisfying certain constraints. Moser and Tardos (2010) have shown that the LLL gives more than just pure existence results: there is an effective randomized algorithm that can be used to find a desired object. In order to analyze this algorithm, Moser and Tardos developed the so-called entropy compression method. It turned out that one could obtain better combinatorial results by a direct application of the entropy compression method rather than simply appealing to the LLL. The aim of this paper is to provide a generalization of the LLL which implies these new combinatorial results. This generalization, which we call the Local Cut Lemma, concerns a random cut in a directed graph with certain properties. Note that our result has a short probabilistic proof that does not use entropy compression. As a consequence, it not only shows that a certain probability is positive, but also gives an explicit lower bound for this probability. As an illustration, we present a new application (an improved lower bound on the number of edges in color-critical hypergraphs) as well as explain how to use the Local Cut Lemma to derive some of the results obtained previously using the entropy compression method.     

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

O (c+d) steps using constant-size queues, where c is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lovász Local Lemma and was not constructive. In this paper, we show how to find such a schedule in time, with probability , for any positive constant β, where is the sum of the lengths of the paths taken by the packets in the network, and m is the number of edges used by some packet in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lovász Local Lemma discovered by Beck. Received: July 8, 1996     

Multivariate Local Polynomial Fitting for Martingale Nonlinear Regression Models

Local polynomial modelling is a useful tool for nonlinear time series analysis. For nonlinear regression models with martingale difference errors, this paper presents a simple proof of local linear and local quadratic fittings under apparently minimal short-range dependence condition. Explicit formulae for the asymptotic bias and asymptotic variance are given, which facilitate numerical evaluations of these important quantities. The general theory is applied to nonparametric partial derivative estimation in nonlinear time series. A bias-adjusted method for constructing confidence intervals for first-order partial derivatives is described. Two examples, including the sunspots data, are used to demonstrate the use of local quadratic fitting for modelling and characterizing nonlinearity in time series data.     

Diffusion in Glassy Polymers: Sorption of a Finite Amount of Solvent

A family of 1-D moving boundary models describing the diffusion of a finite amount of a penetrant in a glassy polymer is studied. Local existence of a unique classical solution is obtained for a generic quasilinear model. Specific data are then chosen which can be found in the literature (cf. [6]) and global existence of the classical solution and its convergence to an equilibrium solution are proven. Finally a rigorous proof is provided for a formal perturbation argument proposed in [6] and used therein to estimate the rate of convergence of the solution towards the equilibrium.     

r-Qsym is free over Sym

Our main result is a proof of the Florent Hivert conjecture [F. Hivert, Local action of the symmetric group and generalizations of quasi-symmetric functions, in preparation] that the algebras of r-Quasi-Symmetric polynomials in x₁,x₂,…,xn are free modules over the ring of Symmetric polynomials. The proof rests on a theorem that reduces a wide variety of freeness results to the establishment of a single dimension bound. We are thus able to derive the Etingof-Ginzburg [P. Etingof, V. Ginzburg, On m-quasi-invariants of a Coxeter group, Mosc. Math. J. 2 (2002) 555-566] Theorem on m-Quasi-Invariants and our r-Quasi-Symmetric result as special cases of a single general principle. Another byproduct of the present treatment is a remarkably simple new proof of the freeness theorem for 1-Quasi-Symmetric polynomials given in [A.M. Garsia, N. Wallach, Qsym over Sym is free, J. Combin. Theory Ser. A 104 (2) (2003) 217-263].     

A Parallel Algorithm for Adaptive Local Refinement of Tetrahedral Meshes Using Bisection

Local mesh refinement is one of the key steps in the implementations of adaptive finite element methods. This paper presents a parallel algorithm for distributed memory parallel computers for adaptive local refinement of tetrahedral meshes using bisection. This algorithm is used in PHG, Parallel Hierarchical Grid (http: //lsec. cc. ac. cn/phg/J, a toolbox under active development for parallel adaptive finite element solutions of partial differential equations. The algorithm proposed is characterized by allowing simultaneous refinement of submeshes to arbitrary levels before synchronization between submeshes and without the need of a central coordinator process for managing new vertices. Using the concept of canonical refinement, a simple proof of the independence of the resulting mesh on the mesh partitioning is given, which is useful in better understanding the behaviour of the bisectioning refinement procedure.AMS subject classifications: 65Y05, 65N50     

The Johansson‐Molloy theorem for DP‐coloring

The aim of this note is twofold. On the one hand, we present a streamlined version of Molloy's new proof of the bound for triangle‐free graphs G, avoiding the technicalities of the entropy compression method and only using the usual “lopsided” Lovász Local Lemma (albeit in a somewhat unusual setting). On the other hand, we extend Molloy's result to DP‐coloring (also known as correspondence coloring), a generalization of list coloring introduced recently by Dvo?ák and Postle.     

The Local Langlands Correspondence for GL n over p-adic fields

We extend our methods from Scholze (Invent. Math. 2012, doi:10.1007/s00222-012-0419-y) to reprove the Local Langlands Correspondence for GL _n over p-adic fields as well as the existence of ?-adic Galois representations attached to (most) regular algebraic conjugate self-dual cuspidal automorphic representations, for which we prove a local-global compatibility statement as in the book of Harris-Taylor (The Geometry and Cohomology of Some Simple Shimura Varieties, 2001). In contrast to the proofs of the Local Langlands Correspondence given by Henniart (Invent. Math. 139(2), 439–455, 2000), and Harris-Taylor (The Geometry and Cohomology of Some Simple Shimura Varieties, 2001), our proof completely by-passes the numerical Local Langlands Correspondence of Henniart (Ann. Sci. Éc. Norm. Super. 21(4), 497–544, 1988). Instead, we make use of a previous result from Scholze (Invent. Math. 2012, doi:10.1007/s00222-012-0419-y) describing the inertia-invariant nearby cycles in certain regular situations.     

Every 8-uniform 8-regular hypergraph is 2-colorable

As is well known, Lovász Local Lemma implies that everyd-uniformd-regular hypergraph is 2-colorable, providedd 9. We present a different proof of a slightly stronger result; everyd-uniformd-regular hypergraph is 2-colorable, providedd 8.Research supported in part by Allon Fellowship and by a grant from the United States Israel Binational Science Foundation.     

A (1 + ϵ)‐approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma*

In his seminal result, Beck gave the first algorithmic version of the Lovász Local Lemma by giving polynomial time algorithms for 2‐coloring and partitioning uniform hypergraphs. His work was later generalized by Alon, and Molloy and Reed. Recently, Czumaj and Scheideler gave an efficient algorithm for 2‐coloring nonuniform hypergraphs. But the partitioning algorithm obtained based on their second paper only applies to a more limited range of hypergraphs, so much so that their work doesn't imply the result of Beck for the uniform case. Here we give an algorithmic version of the general form of the Local Lemma which captures (almost) all applications of the results of Beck and Czumaj and Scheideler, with an overall simpler proof. In particular, if H is a nonuniform hypergraph in which every edge e_i intersects at most |e_i|2^αk other edges of size at most k, for some small constant α, then we can find a partitioning of H in expected linear time. This result implies the result of Beck for uniform hypergraphs along with a speedup in his running time. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

Pool resolution is NP-hard to recognize

A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-complete.     

On a rigidity result of singularities

The aim of this note is to prove, in the spirit of a rigidity result for isolated singularities of Schlessinger see Schlessinger (Invent Math 14:17–26, 1971) or also Kleiman and Landolfi (Compositio Math 23:407–434, 1971), a variant of a rigidity criterion for arbitrary singularities (Theorem 2.1 below). The proof of this result does not use Schlessinger’s Deformation Theory [Schlessinger (Trans Am Math Soc 130:208–222, 1968) and Schlessinger (Invent Math 14:17–26, 1971)]. Instead it makes use of Local Grothendieck-Lefschetz Theory, see (Grothendieck 1968, Éxposé 9, Proposition 1.4, page 106) and a Lemma of Zariski, see (Zariski, Am J Math 87:507–536, 1965, Lemma 4, page 526). I hope that this proof, although works only in characteristic zero, might also have some interest in its own.     

A Revision of the Proof of the Kepler Conjecture

The Kepler conjecture asserts that no packing of congruent balls in three-dimensional Euclidean space has density greater than that of the face-centered cubic packing. The original proof, announced in 1998 and published in 2006, is long and complex. The process of revision and review did not end with the publication of the proof. This article summarizes the current status of a long-term initiative to reorganize the original proof into a more transparent form and to provide a greater level of certification of the correctness of the computer code and other details of the proof. A final part of this article lists errata in the original proof of the Kepler conjecture.