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     

Turánnical hypergraphs

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turán's theorem, which deals with graphs G = ([n],E) such that no member of the restriction set \begin{align*}\mathcal {R}\end{align*} = \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced by \begin{align*}\mathcal {R}\end{align*} = {X∈ \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*}: X ∩ [m]≠??}. That is, we determine the maximal number of edges in an n ‐vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r ‐uniform hypergraph \begin{align*}\mathcal R\end{align*} on vertex set [n] is called Turánnical (respectively ε ‐Turánnical), if for any graph G on [n] with more edges than the Turán number t_r(n) (respectively (1 + ε)t_r(n) ), no hyperedge of \begin{align*}\mathcal {R}\end{align*} induces a copy of K_r in G. We determine the thresholds for random r ‐uniform hypergraphs to be Turánnical and to be ε ‐Turánnical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa‐?uczak‐Rödl Conjecture on Turán's theorem in random graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

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     

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}.     

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     

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     

C‐perfect hypergraphs

Let ${\mathcal{H}}=({{X}},{\mathcal{E}})Let ${\mathcal{H}}=({{X}},{\mathcal{E}})$ be a hypergraph with vertex set X and edge set ${\mathcal{E}}$. A C‐coloring of ${\mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}\in{\mathcal{E}}$ (i.e. no edge is multicolored). We denote by $\bar{\chi}({\mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $\alpha({\mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}\in{\mathcal{E}}$, and $\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E \in {\mathcal{E}}$. The hypergraph ${\mathcal{H}}$ is called C‐perfect if $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$ holds for every induced subhypergraph ${\mathcal{H}}\prime\subseteq{\mathcal{H}}$. If ${\mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${\mathcal{H}}$ with $\tau({\mathcal{H}})\le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010     

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.     

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     

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     

Quasilinear degenerate parabolic equations of Kirchhoff type

We investigate the evolution problem where H is a Hilbert space, A is a self‐adjoint linear non‐negative operator on H with domain D(A), and is a continuous function. We prove that if , and , then there exists at least one global solution, which is unique if either m never vanishes, or m is locally Lipschitz continuous. Moreover, we prove that if for all , then this problem is well posed in H. On the contrary, if for some it happens that for all , then this problem has no solution if with β small enough. We apply these results to degenerate parabolic PDEs with non‐local non‐linearities. Copyright © 1999 John Wiley & Sons, Ltd.     

Crossing numbers of imbalanced graphs

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e>4n edges is at least constant times e³/n². Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d₁?d₂?···?d_n, then the crossing number satisfies \begin{eqnarray*}{\rm{cr}}(G)\geq \frac{c_{1}}{n}\end{eqnarray*} with \begin{eqnarray*}{\textstyle\sum\nolimits_{{{i}}={{{1}}}}^{{{n}}}}{{id}}_{{{i}}}^{{{3}}}-{{c}}_{{{2}}}{{n}}^{{{2}}}\end{eqnarray*}, and that this bound is tight apart from the values of the constants c₁, c₂>0. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010     

Compactness Conditions for the Green Operator in Lp(ℝ) Corresponding to a General Sturm–Liouville Operator

We consider the equation ℝ, where , for ℝ, (ℝ), (ℝ), (ℝ), (ℝ) := C(ℝ)). We give necessary and sufficient conditions under which, regardless of , the following statements hold simultaneously: I) For any (ℝ) Equation (0.1) has a unique solution (ℝ) where $\int ^{\infty}_{-\infty}$ ℝ. II) The operator (ℝ) → (ℝ) is compact. Here is the Green function corresponding to (0.1). This result is applied to study some properties of the spectrum of the Sturm–Liouville operator.     

Uniqueness of Integrable Solutions ∇ζ = Gζ, ζ∣Γ = 0 for Integrable Tensor-Coefficients G and Applications to Elasticity

Let be bounded Lipschitz and relatively open. We show that the solution to the linear first order system 1 : (1) vanishes if and , (e.g. ). We prove to be a norm if with , for some p, q > 1 with 1/p + 1/q = 1 and . We give a new proof for the so called ‘in-finitesimal rigid displacement lemma’ in curvilinear coordinates: Let , satisfy for some with . Then there are and a constant skew-symmetric matrix , such that . (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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}.     

Comparing Packing Measures to Hausdorff Measures on the Line

For each 0 < s < 1, define where , denote respectively the s‐dimensional packing measure and Hausdorff measure, and the infimum is taken over all the sets E ⊂ R with . In this paper we give a nontrivial estimation of c(s), namely, for each 0 < s < 1, where . As an application, we obtain a lower density theorem for Hausdorff measures.     

Fourth-order accurate one-step integration methods with large imaginary stability limits

One-step integration methods of fourth-order accuracy using an odd number of function evaluations K, to solve dy/dt = A · y, are proposed. These methods have an imaginary stability limit \documentclass{article}\pagestyle{empty}\begin{document}$ S_{1\;} = \sqrt {(K - 1)^2 - 4} $\end{document}. In the case K = 5 the Kutta-Merson method results.     

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.     

On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022