Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC‐nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC‐nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC‐nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC‐net rules. We present read‐once MC‐nets, a new class of MC‐nets that is provably more compact than basic MC‐nets, while retaining the attractive computational properties of basic MC‐nets. We show how the techniques we develop for read‐once MC‐nets can be applied to other domains, in particular, computing solution concepts in network flow games on series‐parallel networks (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On second order weakly hyperbolic equations with oscillating coefficients and regularity loss of the solutions

Regularity of the solution for the wave equation with constant propagation speed is conserved with respect to time, but such a property is not true in general if the propagation speed is variable with respect to time. The main purpose of this paper is to describe the order of regularity loss of the solution due to the variable coefficient by the following four properties of the coefficient: “smoothness”, “oscillations”, “degeneration” and “stabilization”. Actually, we prove the Gevrey and C^∞ well‐posedness for the wave equations with degenerate coefficients taking into account the interactions of these four properties. Moreover, we prove optimality of these results by constructing some examples (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nonlocal Tug‐of‐War and the Infinity Fractional Laplacian

Motivated by the “tug‐of‐war” game studied by Peres et al. in 2009, we consider a nonlocal version of the game that goes as follows: at every step two players pick, respectively, a direction and then, instead of flipping a coin in order to decide which direction to choose and then moving a fixed amount ϵ > 0 (as is done in the classical case), it is an s‐stable Levy process that chooses at the same time both the direction and the distance to travel. Starting from this game, we heuristically derive a deterministic nonlocal integrodifferential equation that we call the “infinity fractional Laplacian.” We study existence, uniqueness, and regularity, both for the Dirichlet problem and for a double‐obstacle problem, both problems having a natural interpretation as tug‐of‐war games. © 2011 Wiley Periodicals, Inc.     

The phase transition in inhomogeneous random graphs

The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models. One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007     

The computational complexity of two‐state spin systems

The subject of this article is spin‐systems as studied in statistical physics. We focus on the case of two spins. This case encompasses models of physical interest, such as the classical Ising model (ferromagnetic or antiferromagnetic, with or without an applied magnetic field) and the hard‐core gas model. There are three degrees of freedom, corresponding to our parameters β, γ, and μ. Informally, β represents the weights of edges joining pairs of “spin blue” sites, γ represents the weight of edges joining pairs of “spin green” sites, and μ represents the weight of “spin green” sites. We study the complexity of (approximately) computing the partition function in terms of these parameters. We pay special attention to the symmetric case μ = 1. Exact computation of the partition function Z is NP‐hard except in the trivial case βγ = 1, so we concentrate on the issue of whether Z can be computed within small relative error in polynomial time. We show that there is a fully polynomial randomised approximation scheme (FPRAS) for the partition function in the “ferromagnetic” region βγ ≥ 1, but (unless RP = NP) there is no FPRAS in the “antiferromagnetic” region corresponding to the square defined by 0 < β < 1 and 0 < γ < 1. Neither of these “natural” regions—neither the hyperbola nor the square—marks the boundary between tractable and intractable. In one direction, we provide an FPRAS for the partition function within a region which extends well away from the hyperbola. In the other direction, we exhibit two tiny, symmetric, intractable regions extending beyond the antiferromagnetic region. We also extend our results to the asymmetric case μ ≠ 1. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 133–154, 2003     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

The Effects of Project‐Based Learning on Students' Academic Achievement,Attitude, and Retention of Knowledge: The Subject of “Electricity in Our Lives”

The aim of this study is to analyze the effects of project‐based learning on students' academic achievement, attitude, and retention of knowledge in relation to the subject of “Electricity in Our Lives” in a fourth‐grade science course. The study was conducted in a quasi‐experimental design as a “pre‐test, post‐test with control group.” In the experimental group, the unit was taught through the project‐based learning method. The measuring tools were administered to both groups before and after the applications. To perfectly analyze the “process” of the method, seven different learning assessment “forms” were administered to the students. The findings of the forms indicated that the students learn to construct their own learning and to evaluate changes in their own behavior through the application of the method. The application of different methods between both groups had a statistically significant effect in terms of academic achievement, (F(1,112) = 46.78, p = .000) and of retention of knowledge (F(1,112) = 35.24, p = .000). However, there were no statistically significant effects from being in different groups for the attitudes of students (F(1,112) = .99, p = .321). For the students, being in the project‐based learning groups resulted in better academic achievement and retention of knowledge than being in the traditional teaching group.     

Understanding preservation theorems,II

We present an exposition of much of Sections VI.3 and XVIII.3 from Shelah's book Proper and Improper Forcing. This covers numerous preservation theorems for countable support iterations of proper forcing, including preservation of the property “no new random reals over V ”, the property “reals of the ground model form a non‐meager set”, the property “every dense open set contains a dense open set of the ground model”, and preservation theorems related to the weak bounding property, the weak ^ωω ‐bounding property, and the property “the set of reals of the ground model has positive outer measure” (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Quantized CP approximation and sparse tensor interpolation of function‐generated data

In this article, we consider the iterative schemes to compute the canonical polyadic (CP) approximation of quantized data generated by a function discretized on a large uniform grid in an interval on the real line. This paper continues the research on the quantics‐tensor train (QTT) method (“O(d log N)‐quantics approximation of N‐d tensors in high‐dimensional numerical modeling” in Constructive Approximation, 2011) developed for the tensor train (TT) approximation of the quantized images of function related data. In the QTT approach, the target vector of length 2^L is reshaped to a Lth‐order tensor with two entries in each mode (quantized representation) and then approximated by the QTT tensor including 2r²L parameters, where r is the maximal TT rank. In what follows, we consider the alternating least squares (ALS) iterative scheme to compute the rank‐r CP approximation of the quantized vectors, which requires only 2rL?2^L parameters for storage. In the earlier papers (“Tensors‐structured numerical methods in scientific computing: survey on recent advances” in Chemom Intell Lab Syst, 2012), such a representation was called Q_Can format, whereas in this paper, we abbreviate it as the QCP (quantized canonical polyadic) representation. We test the ALS algorithm to calculate the QCP approximation on various functions, and in all cases, we observed the exponential error decay in the QCP rank. The main idea for recovering a discretized function in the rank‐r QCP format using the reduced number of the functional samples, calculated only at O(2rL) grid points, is presented. The special version of the ALS scheme for solving the arising minimization problem is described. This approach can be viewed as the sparse QCP‐interpolation method that allows to recover all 2rL representation parameters of the rank‐r QCP tensor. Numerical examples show the efficiency of the QCP‐ALS‐type iteration and indicate the exponential convergence rate in r.     

Characteristic exponents of semialgebraic singularities

Let X be a semialgebraic (or algebraic) set and let x₀ ∈ X be a singular point. There are some topological cycles of different dimensions contained in a small neighbourhood of x₀ in X. All these cycles vanish in x₀. The paper is devoted to “vanishing rates” of these cycles, which we call “characteristic exponents”. We prove that the characteristic exponents are invariant under bi‐Lipschitz transformations. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An optimal family of exponentially accurate one‐bit Sigma‐Delta quantization schemes

Sigma‐delta modulation is a popular method for analog‐to‐digital conversion of bandlimited signals that employs coarse quantization coupled with oversampling. The standard mathematical model for the error analysis of the method measures the performance of a given scheme by the rate at which the associated reconstruction error decays as a function of the oversampling ratio λ. It was recently shown that exponential accuracy of the form O(2^−rλ) can be achieved by appropriate one‐bit sigma‐delta modulation schemes. By general information‐entropy arguments, r must be less than 1. The current best‐known value for r is approximately 0:088. The schemes that were designed to achieve this accuracy employ the “greedy” quantization rule coupled with feedback filters that fall into a class we call “minimally supported.” In this paper, we study the discrete minimization problem that corresponds to optimizing the error decay rate for this class of feedback filters. We solve a relaxed version of this problem exactly and provide explicit asymptotics of the solutions. From these relaxed solutions, we find asymptotically optimal solutions of the original problem, which improve the best‐known exponential error decay rate to r ≈ 0.102. Our method draws from the theory of orthogonal polynomials; in particular, it relates the optimal filters to the zero sets of Chebyshev polynomials of the second kind. © 2011 Wiley Periodicals, Inc.     

On pseudolinearity and generic pairs

We continue the study of the connection between the “geometric” properties of SU ‐rank 1 structures and the properties of “generic” pairs of such structures, started in [8]. In particular, we show that the SU‐rank of the (complete) theory of generic pairs of models of an SU ‐rank 1 theory T can only take values 1 (if and only if T is trivial), 2 (if and only if T is linear) or ω, generalizing the corresponding results for a strongly minimal T in [3]. We also use pairs to derive the implication from pseudolinearity to linearity for ω ‐categorical SU ‐rank 1 structures, established in [7], from the conjecture that an ω ‐categorical supersimple theory has finite SU ‐rank, and find a condition on generic pairs, equivalent to pseudolinearity in the general case (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Counting the onion

Iteratively computing and discarding a set of convex hulls creates a structure known as an “onion.” In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is Θ(n^2/3). Additionally, we show that in general the bound is Θ(n^2/(d+1)) for points distributed in a d‐dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full‐dimensional shape with a nonempty interior. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Integral and Asymptotic Properties of Solitary Waves in Deep Water

We consider two‐ and three‐dimensional gravity and gravity‐capillary solitary water waves in infinite depth. Assuming algebraic decay rates for the free surface and velocity potential, we show that the velocity potential necessarily behaves like a dipole at infinity and obtain a related asymptotic formula for the free surface. We then prove an identity relating the “dipole moment” to the kinetic energy. This implies that the leading‐order terms in the asymptotics are nonvanishing and in particular that the angular momentum is infinite. Lastly we prove that the “excess mass” vanishes. © 2018 the Authors. Communications on Pure and Applied Mathematics is published by the Courant Institute of Mathematical Sciences and Wiley Periodicals, Inc.     

Efficient algorithms for three‐dimensional axial and planar random assignment problems

Beautiful formulas are known for the expected cost of random two‐dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP‐hard. For 3‐dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear‐time algorithm that, with high probability, finds a solution of cost O(n^–1+o(1)). For 3‐dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching‐based algorithm that with high probability returns a solution with cost O(n log n). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 160–196, 2015     

Homogenization and Enhancement of the G‐Equation in Random Environments

We study the homogenization of a G‐equation that is advected by a divergence free “small mean” stationary vector field in a general ergodic random environment. We prove that the averaged equation is an anisotropic deterministic G‐equation, and we give necessary and sufficient conditions for enhancement. Since the problem is not assumed to be coercive, it is not possible to have uniform bounds for the solutions. In addition, as we show, the associated minimal (first passage) time function does not satisfy, in general, the uniform integrability condition that is necessary to apply the subadditive ergodic theorem. We overcome these obstacles by (i) establishing a new reachability (controllability) estimate for the minimal function and (ii) constructing, for each direction and almost surely, a random sequence that has both a long‐time averaged limit (due to the subadditive ergodic theorem) and stays asymptotically close to the minimal time. © 2013 Wiley Periodicals, Inc.     

Ancestors and descendants in evolving k‐tree models

We consider several random graph models based on k‐trees, which can be generated by applying the probabilistic growth rules “uniform attachment”, “preferential attachment”, or a “saturation”‐rule, respectively, but which also can be described in a combinatorial way. For all of these models we study the number of ancestors and the number of descendants of nodes in the graph by carrying out a precise analysis which leads to exact and limiting distributional results. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 465–489, 2014