Decomposition of Log Crepant Birational Morphisms between Log Terminal Surfaces

We prove that every log crepant birational morphism between log terminal surfaces can be decomposed into log flopping type divisorial contraction morphisms and log blowdowns. Repeating these two kinds of contractions, we reach a minimal log minimal surface from any log minimal surface.     

Log‐symmetric regression models: information criteria and application to movie business and industry data with economic implications

This work deals with log‐symmetric regression models, which are particularly useful when the response variable is continuous, strictly positive, and following an asymmetric distribution, with the possibility of modeling atypical observations by means of robust estimation. In these regression models, the distribution of the random errors is a member of the log‐symmetric family, which is composed by the log‐contaminated‐normal, log‐hyperbolic, log‐normal, log‐power‐exponential, log‐slash and log‐Student‐t distributions, among others. One way to select the best family member in log‐symmetric regression models is using information criteria. In this paper, we formulate log‐symmetric regression models and conduct a Monte Carlo simulation study to investigate the accuracy of popular information criteria, as Akaike, Bayesian, and Hannan‐Quinn, and their respective corrected versions to choose adequate log‐symmetric regressions models. As a business application, a movie data set assembled by authors is analyzed to compare and obtain the best possible log‐symmetric regression model for box offices. The results provide relevant information for model selection criteria in log‐symmetric regressions and for the movie industry. Economic implications of our study are discussed after the numerical illustrations.     

Letters of a Bi-rationalist. VII Ordered termination

To construct a resulting model in the LMMP, it is sufficient to prove the existence of log flips and their termination for some sequences. We prove that the LMMP in dimension d − 1 and the termination of terminal log flips in dimension d imply, for any log pair of dimension d, the existence of a resulting model: a strictly log minimal model or a strictly log terminal Mori log fibration, and imply the existence of log flips in dimension d + 1. As a consequence, we prove the existence of a resulting model of 4-fold log pairs, the existence of log flips in dimension 5, and Geography of log models in dimension 4. Published in Russian in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2009, Vol. 264, pp. 184–208. To V.A. Iskovskikh, who has greatly shaped my vision of mathematics     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.     

On the linear independence measure of logarithms of rational numbers

In this paper we give a general theorem on the linear independence measure of logarithms of rational numbers and, in particular, the linear independence measure of and of . We also give a method to search for polynomials of smallest norm on a real interval which may be suitable for computing or improving the linear independence measure of logarithms of rational numbers.

     

Ideal-adic semi-continuity problem for minimal log discrepancies

We discuss the ideal-adic semi-continuity problem for minimal log discrepancies by Musta??. We study the purely log terminal case, and prove the semi-continuity of minimal log discrepancies when a Kawamata log terminal triple deforms in the ideal-adic topology.     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

Difference sets and shifted primes

We show that if A is a subset of {1, …, n} which has no pair of elements whose difference is equal to p ? 1 with p a prime number, then the size of A is O(n(log log n)^{?c(log log log log log n)}) for some absolute c > 0.     

The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

Let n = (p − 1) · p ^k , where p is a prime number such that 2 is a primitive root modulo p, and 2 ^p−1 − 1 is not a multiple of p ². For a standard basis of the field GF(2 ⁿ ), a multiplier of complexity O(log log p)n log n log log _p n and an inverter of complexity O(log p log log p)n log n log log _p n are constructed. In particular, in the case p = 3 the upper bound

Categorical representation of locally noetherian log schemes

In this paper, we show that for a certain fairly general class of log schemes, the structure of the log scheme may be recovered entirely from the purely categorical structure of a certain associated category of log schemes of finite type over the given log scheme. This result is motivated partly by Grothendieck's anabelian philosophy and partly by general philosophical considerations concerning the importance of categories as a foundation for mathematics.     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Growth conditions for entire functions with only bounded Fatou components

Let f be a transcendental entire function of order less than 1/2. Denote the maximum and minimum modulus of f by M(r, f) = max{|f(z)|: |z| = r} and m(r, f) = min{|f(z)|: |z| = r}. We obtain a minimum modulus condition satisfied by many f of order zero that implies all Fatou components are bounded. A special case of our result is that if

对Baker~[1]-Mahler~[2]一个定理的注记

<正> 对任意实数x,定义‖x‖=max(x-[x],[x]+1-x).设a_1,…,a_(k-1)是互不相等的非零整数,a是适合(a,a_1,…,a_(k-1)=1的正整数,r是正整数.置     

How many elements are needed to generate a finite group with good probability?

We prove that for any real number 0<α<1, there exists a constantc _α such that the probability of generating a finite groupG with [d(G)+c _α log log |G| log log log |G|] elements is at least α.     

Logarithmic geometry and algebraic stacks

We construct algebraic moduli stacks of log structures and give stack-theoretic interpretations of K. Kato's notions of log flat, log smooth, and log étale morphisms. In the last section we describe the local structure of these moduli stacks in terms of toric stacks.     

On log canonical divisors that are log quasi-numerically positive

Let (X Δ) be a four-dimensional log variety that is projective over the field of complex numbers. Assume that (X, Δ) is not Kawamata log terminal (klt) but divisorial log terminal (dlt). First we introduce the notion of “log quasi-numerically positive”, by relaxing that of “numerically positive”. Next we prove that, if the log canonical divisorK _X+Δ is log quasi-numerically positive on (X, Δ) then it is semi-ample.     

The chromatic number of random graphs

Let χ(G(n, p)) denote the chromatic number of the random graphG(n, p). We prove that there exists a constantd ₀ such that fornp(n)>d ₀,p(n)→0, the probability that $$\frac{{np}}{{2 log np}}\left( {1 + \frac{{\log log np - 1}}{{\log np}}} \right)< \chi (G(n,p))< \frac{{np}}{{2 log np}}\left( {1 + \frac{{30 \log \log np}}{{\log np}}} \right)$$ tends to 1 asn→∞.     

Log canonical foliation singularities on surfaces

We give a classification of the dual graphs of the exceptional divisors on the minimal resolutions of log canonical foliation singularities on surfaces. As an application, we show the set of foliated minimal log discrepancies for foliated surface triples satisfies the ascending chain condition and a Grauert–Riemenschneider–type vanishing theorem for foliated surfaces with special log canonical foliation singularities.     

Nearly optimal distributed edge coloring in O(log log n) rounds

An extremely simple distributed randomized algorithm is presented which with high probability properly edge colors a given graph using (1 + ϵ)Δ colors, where Δ is the maximum degree of the graph and ϵ is any given positive constant. The algorithm is very fast. In particular, for graphs with sufficiently large vertex degrees (larger than polylog n, but smaller than any positive power of n), the algorithm requires only O(log log n) communication rounds. The algorithm is inherently distributed, but can be implemented on the PRAM, where it requires O(mΔ) processors and O(log Δ log log n) time, or in a sequential setting, where it requires O(mΔ) time. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 385–405 (1997)     

AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

We present an algorithm to compute, inO(m + n log n) time, a maximum clique in circular-arc graphs (withnvertices andmedges) provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the time complexity isO(m). The algorithm operates on the geometric structure of the circular arcs, radially sweeping their endpoints; it uses a very simple data structure consisting of doubly linked lists. Previously, the best time bound for this problem wasO(m log log n + n log n), using an algorithm that solved an independent subproblem for each of thencircular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log nfactor from the running time of earlier algorithms. For vertex-weighted circular-arc graphs, it is possible to use our approach to obtain anO(m log log n + n log n) algorithm for finding a maximum-weight clique—which matches the best known algorithm.