A Self‐Dual Polar Factorization for Vector Fields

We show that any nondegenerate vector field u in \begin{align*}L^{\infty}(\Omega, \mathbb{R}^N)\end{align*}, where Ω is a bounded domain in \begin{align*}\mathbb{R}^N\end{align*}, can be written as \begin{align*}u(x)= \nabla_1 H(S(x), x)\quad {\text for a.e.\ x \in \Omega}\end{align*}}, where S is a measure‐preserving point transformation on Ω such that \begin{align*}S^2=I\end{align*} a.e. (an involution), and \begin{align*}H: \mathbb{R}^N \times \mathbb{R}^N \to \mathbb{R}\end{align*} is a globally Lipschitz antisymmetric convex‐concave Hamiltonian. Moreover, u is a monotone map if and only if S can be taken to be the identity, which suggests that our result is a self‐dual version of Brenier's polar decomposition for the vector field as \begin{align*}u(x)=\nabla \phi (S(x))\end{align*}, where ? is convex and S is a measure‐preserving transformation. We also describe how our polar decomposition can be reformulated as a (self‐dual) mass transport problem. © 2012 Wiley Periodicals, Inc.     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Path homomorphisms,graph colorings,and boolean matrices

We investigate bounds on the chromatic number of a graph G derived from the nonexistence of homomorphisms from some path \begin{eqnarray*}\vec{P}\end{eqnarray*} into some orientation \begin{eqnarray*}\vec{G}\end{eqnarray*} of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path \begin{eqnarray*}\vec{P}\end{eqnarray*} depends on the relation between the “algebraic length” and “derived algebraic length” of \begin{eqnarray*}\vec{P}\end{eqnarray*}. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 198–209, 2010     

Giant components in Kronecker graphs

Let \begin{align*}n\in\mathbb{N}\end{align*}, 0 <α,β,γ< 1. Define the random Kronecker graph K(n,α,γ,β) to be the graph with vertex set \begin{align*}\mathbb{Z}_2^n\end{align*}, where the probability that u is adjacent to v is given by p_u,v =α ^{u ? v} γ^{( 1‐u )?( 1‐v )}β^{n‐ u ? v ‐( 1‐u )?( 1‐v )}. This model has been shown to obey several useful properties of real‐world networks. We establish the asymptotic size of the giant component in the random Kronecker graph.© 2011 Wiley Periodicals, Inc. Random Struct. Alg.,2011     

Families of pairs of graphs with a large number of common cards

The vertex‐deleted subgraph G?v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least \begin{eqnarray*}2\lfloor\frac{1}{3}(n-1)\rfloor\end{eqnarray*} common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have \begin{eqnarray*}\frac{2}{3}(n+5-2\sqrt{3n+6})\end{eqnarray*} common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n≥10. We also present infinite families of pairs of forests and pairs of trees with \begin{eqnarray*}2\lfloor\frac{1}{3}(n-4)\rfloor\end{eqnarray*} and \begin{eqnarray*}2\lfloor\frac{1}{3}(n-5)\rfloor\end{eqnarray*} common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146–163, 2010     

Local superconvergence of the derivative for tensor‐product block FEM

In this article, we shall discuss local superconvergence of the derivative for tensor‐product block finite elements over uniform partition for three‐dimensional Poisson's equation on the basis of Liu and Zhu (Numer Methods Partial Differential Eq 25 (2009) 999–1008). Assume that odd m ≥ 3, x₀ is an inner locally symmetric point of uniform rectangular partition \begin{align*}\mathcal{T}_{h}\end{align*} and ρ(x₀,?Ω) means the distance between x₀ and boundary ?Ω. Combining the symmetry technique (Wahlbin, Springer, 1995; Schatz, Sloan, and Wahlbin, SIAM J Numer Anal 33 (1996), 505–521; Schatz, Math Comput 67 (1998), 877–899) with weak estimates for tensor‐product block finite elements of degree m ≥ 3 [see Liu and Zhu, Numer Methods Partial Differential Eq 25 (2009) 999–1008] and the finite element theory of Green function in ??³ presented in this article, we propose the \begin{align*}O(h^{m+3}|\ln h|^{\frac{4}{3}}+h^{2m+2}|\ln h|^{\frac{4}{3}}\rho(x_{0},\partial\Omega)^{-m})\end{align*} convergence of the derivatives for tensor‐product block finite elements of degree m ≥ 3 on x₀. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 457–475, 2012     

Unions and Intersections of Families of Lp-Spaces

Let L^Ψ and E^Ψ be the ORLICZ space and the space of finite elements respectively, on a measure space (Ω, Σ, μ), and let T ? (0, ∞). It is proved that if inf {p: p ? T} ? T or sup {p: p ? T} ? T and μ is an infinite atomless measure, then there is no ORLICZ function Ψ such that: \documentclass{article}\pagestyle{empty}\begin{document}$ L^\varphi = Lin\mathop { \cup L^p }\limits_{p\varepsilon T} $\end{document} or \documentclass{article}\pagestyle{empty}\begin{document}$ E^\varphi = Lin\mathop { \cup L^p }\limits_{p\varepsilon T} $\end{document} and moreover, there is no ORLICZ function Ψ such that: \documentclass{article}\pagestyle{empty}\begin{document}$ L^\varphi = Lin\mathop { \cap L^p }\limits_{p\varepsilon T} $\end{document} or \documentclass{article}\pagestyle{empty}\begin{document}$ E^\varphi = Lin\mathop { \cap L^p }\limits_{p\varepsilon T} $\end{document}.     

Balanced judicious bipartitions of graphs

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if G is a graph with minimum degree of at least 2 then V(G) admits a balanced bipartition V₁, V₂ such that for each i, G has at most |E(G)|/3 edges with both ends in V_i. The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131–143 shows that this conjecture holds for regular graphs G(i.e., when Δ(G)=δ(G)). We prove this conjecture for graphs G with \begin{eqnarray*}\Delta(G)\le\frac{7}{5}\delta(G)\end{eqnarray*}; hence, it holds for graphs ]ensuremathG with \begin{eqnarray*}\delta(G)\ge\frac{5}{7}|V(G)|\end{eqnarray*}. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210–225, 2010     

The PENROSE Transform for Bundles Non-Trivial on the General Line

Let L₀ be a fixed projective line in CP ³ and let M ? C ⁴ be the complexified MINKOWSKI space interpreted as the manifold of all projective lines L ? CP ³ with L ∩ L ₀ ?? Ø. Let D ? M , D ′ ? CP ³/ L ₀ be open sets such that \documentclass{article}\pagestyle{empty}\begin{document}$ D' = \mathop \cup \limits_{L \in D} $\end{document}. Under certain topological conditions on D, R. S. WARD'S PENROSE transform sets up an 1–1 correspondence between holomorphic vector bundles over D ′ trivial over each L ? D and holomorphic connections with anti-self-dual curvature over D (anti-self-dual YANG-MILLIS fields). In the present paper WARD'S construction is generalized to holomorphic vector bundles E over D′ satisfying the condition that \documentclass{article}\pagestyle{empty}\begin{document}$ E|_L \cong E|_{\tilde L} $\end{document} for all \documentclass{article}\pagestyle{empty}\begin{document}$ L,\tilde L \in D $\end{document}.     

Neumann‐Neumann methods for a DG discretization on geometrically nonconforming substructures

A discontinuous Galerkin discretization for second order elliptic equations with discontinuous coefficients in 2D is considered. The domain of interest Ω is assumed to be a union of polygonal substructures Ω_i of size O(H_i). We allow this substructure decomposition to be geometrically nonconforming. Inside each substructure Ω_i, a conforming finite element space associated to a triangulation \begin{align*} {\mathcal{T}}_{h_i}(\Omega_i)\end{align*} is introduced. To handle the nonmatching meshes across ?Ω_i, a discontinuous Galerkin discretization is considered. In this article, additive and hybrid Neumann‐Neumann Schwarz methods are designed and analyzed. Under natural assumptions on the coefficients and on the mesh sizes across ?Ω_i, a condition number estimate \begin{align*} C(1 + \max_i\log \frac{H_i}{h_i})^2\end{align*} is established with C independent of h_i, H_i, h_i/h_j, and the jumps of the coefficients. The method is well suited for parallel computations and can be straightforwardly extended to three dimensional problems. Numerical results are included. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2012     

Critical behavior in inhomogeneous random graphs

We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W. In this case, the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power‐law case, i.e., the case where \begin{align*}{\mathbb{P}}(W\geq k)\end{align*} is proportional to k^‐(τ‐1) for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when \begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} for all k ≥ 1 and some τ > 4 and c > 0, the largest critical connected component in a graph of size n is of order n^2/3, as it is for the critical Erd?s‐Rényi random graph. When, instead, \begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} for k large and some τ∈(3,4) and c > 0, the largest critical connected component is of the much smaller order n^{(τ‐2)/(τ‐1)}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013     

What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?

A digraph D with n vertices is said to be decomposable into a set S of dicycles if every arc of D is contained in exactly one member of S. Counterexamples are given to the following conjectures which are generalizations of three well-known conjectures by G. Hajós, P. Erd?s, and P.J. Kelly: (1) [B. Jackson] Every eulerian-oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{n}{2} $\end{document} dicycles. (2) [W. Bienia & H. Meyniel] Every eulerian digraph is decomposable into at most n dicycles. Certain observations lead us to make three other conjectures: (a) Every eulerian-oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{2n}}{3} $\end{document} dicycles. (b) Every symmetric digraph with n > 1 is decomposable into at most 2n – 3 dicycles. (c) Every eulerian digraph with n > 1 is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{8n}}{3} $\end{document} – 3 dicycles.     

Projective limits of finite decomposition systems

Special finite topological decomposition systems were used to get compactifications of topological spaces in [6]. In this paper the notion of finite decomposition systems is applied for topological measure spaces. We get two canonical topological measure spaces X_∞ and X_∞^d being projective limits of (discrete) finite decomposition systems for each topological measure space X = (X, O, A, P) and each net (A_α) α ? I of upward filtering finite σ-algebras in A. X_∞ is a compact topological measure space and the idea to construct is the same as used in [6]. The compactifications of [6] are cases of some special X_∞. Further on we obtain that each measurable set of the remainder of X_∞ has measure zero with respect to the limit measure P_∞ (Theorem 1). X_∞^d is the STONE representation space X(\documentclass{article}\pagestyle{empty}\begin{document}$ \mathop \cup \limits_{\alpha \in I} A\alpha $\end{document}) of \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop \cup \limits_{\alpha \in I} A\alpha $\end{document} A_α, hence a Boolean measure space with regular Borel measure. Some measure theoretical and topological relations between X, X(\documentclass{article}\pagestyle{empty}\begin{document}$ \mathop \cup \limits_{\alpha \in I} A\alpha $\end{document}) and x(A) where x(A) is the Stone representation space of A, are given in Theorem 2. and 4. As a corollary from Theorem 2. we get a measure theoretical-topological version to the Theorem of Alexandroff Hausdorff for compact T₂ measure spaces x with regular Borel measure (Theorem 3.).     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

Factorization theorems for some scales of operator ideals

Let ??_p and ?_p denote the operator ideals generated by the approximation numbers and entropy numbers, respectively. If 0<p,q< ∞ and \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{1}{p} + \frac{1}{q} = \frac{1}{r}, $\end{document} then ??_p °_q=??_r and ?_p °_q=?_r.     

Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n^‐c, with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ? n and M ≤ /2, is “nearly unique”. More precisely, given a maximum cut C of G_n,M, we can obtain all maximum cuts by moving at most \begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*} vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On the number of subtrees for almost all graphs

In this article it is shown that the number of common edges of two random subtrees of K_n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.     

Dirac's theorem for random graphs

A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \begin{align*}\left\lceil n/2 \right\rceil\end{align*} is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if p ? log n/n, then a.a.s. every subgraph of G(n,p) with minimum degree at least (1/2 + o (1) )np is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability p and the value of the constant 1/2 are asymptotically best possible. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_ij) with \begin{align*}\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0\end{align*} and a (small) k × k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁,…,S_k} of {1,…n} which maximizes \begin{align*}\sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}\end{align*}. We design a polynomial time approximation algorithm that achieves an approximation ratio of \begin{align*}\frac{R(B)^2}{C(B)}\end{align*}, where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_ij = 〈v_i,v_j〉 is the Gram matrix representation of B for some \begin{align*}v_1,\ldots,v_k\in \mathbb{R}^k\end{align*} then R(B) is the minimum radius of a Euclidean ball containing the points {v₁,…,v_k}. The parameter C(B) is defined as the maximum over all measurable partitions {A₁,…,A_k} of \begin{align*}\mathbb{R}^{k-1}\end{align*} of the quantity \begin{align*}\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle\end{align*}, where for i∈{1,…,k} the vector \begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*} is the Gaussian moment of A_i, i.e., \begin{align*}z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx\end{align*}. We also show that for every ε > 0, achieving an approximation guarantee of \begin{align*}(1-\varepsilon)\frac{R(B)^2}{C(B)}\end{align*} is Unique Games hard. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013