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.     

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     

Incomplete Self‐Similar Blow‐Up in a Semilinear Fourth‐Order Reaction‐Diffusion Equation

Blow‐up behavior for the fourth‐order semilinear reaction‐diffusion equation (1) is studied. For the classic semilinear heat equation from combustion theory (2) various blow‐up patterns were investigated since 1970s, while the case of higher‐order diffusion was studied much less. Blow‐up self‐similar solutions of (1) of the form are constructed. These are shown to admit global similarity extensions for t > T : The continuity at t = T is preserved in the sense that This is in a striking difference with blow‐up for (2) , which is known to be always complete in the sense that the minimal (proper) extension beyond blow‐up is u(x, t) ≡+∞ for t > T . Difficult fourth‐order dynamical systems for extension pairs {f(y), F(y)} are studied by a combination of various analytic, formal, and numerical methods. Other nonsimilarity patterns for (1) with nongeneric complete blow‐up are also discussed.     

On <Emphasis Type="Italic">g</Emphasis>-functions for countable state subshifts

For a very ample line bundle L on a smooth projective algebraic curve C, we prove that, under some circumstances on positive integers \(\gamma , d\), if one had \(\dim V^{d-1}_{d}(L)=d-1-\gamma \), then the scheme \(V^{\gamma +2}_{\gamma +3}(L)\), if non-empty, would be 2-dimensional. Furthermore, for a 2-very ample line bundle L on C and an integer d, \(4\le d\le h^0(L)-2\), it will be proved that the dimension of the scheme \( V^{d-1}_{d}(L)\) cannot attain its maximum value, i.e. \(d-2\). This will be used to prove irreduciblity of the highest secant loci of L, namely \(V^{h^0(L)-2}_{h^0(L)-1}(L)\). Then we discuss on the existence of very ample line bundles having reducible highest secant loci on k-gonal curves. Extending a well-known result of Montserrat Teixidor to secant loci, our results answer a question proposed and left unanswered recently by Marian Aprodu and Edoardo Sernesi.     

Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs

We present an algorithm for finding shortest surface non-separating cycles in graphs embedded on surfaces in time, where V is the number of vertices in the graph and g is the genus of the surface. If , this represents an improvement over previous results by Thomassen, and Erickson and Har-Peled. We also give algorithms to find a shortest non-contractible cycle in time, which improves previous results for fixed genus. This result can be applied for computing the face-width and the non-separating face-width of embedded graphs. Using similar ideas we provide the first near-linear running time algorithm for computing the face-width of a graph embedded on the projective plane, and an algorithm to find the face-width of embedded toroidal graphs in time.     

Inexpensive d‐dimensional matchings

Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ edges of the complete d‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d‐dimensional matching is at least $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d³n^1?(2/d)+d¹⁵ for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002     

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     

Global mild solutions of Navier‐Stokes equations

We establish a global well‐posedness of mild solutions to the three‐dimensional, incompressible Navier‐Stokes equations if the initial data are in the space ${\cal{X}}^{-1}$ defined by \input amssym ${\cal{X}}^{‐1} = \{f \in {\cal{D}}^\prime(R^3): \int_{{\Bbb{R}}^3}|\xi|^{‐1}|\widehat{f}|d\xi < \infty\}$ and if the norms of the initial data in ${\cal{X}}^{-1}$ are bounded exactly by the viscosity coefficient μ. © 2010 Wiley Periodicals, Inc.     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.     

Weak and strong solvability of parabolic variational inequalities in Banach spaces

We consider parabolic variational inequalities having the strong formulation

Regularity of renormalized solutions in the Boltzmann equation with long‐range interactions

It is well‐established that renormalized solutions of the Boltzmann equation enjoy some kind of regularity, or at least compactness, in the velocity variable when the angular collision kernel is nonintegrable. However, obtaining explicit estimates in convenient and natural functional settings proves rather difficult. In this work, we derive a velocity smoothness estimate from the a priori control of the renormalized dissipation. As a direct consequence of our result, we show that, in the presence of long‐range interactions, any renormalized solution F(t, x, v) to the Boltzmann equation satisfies locally ${\textstyle{F \over {1 + F}}} \in W_{t,x,v}^{s,p}$ for every $1 \le p \le {\textstyle{D \over {D - 1}}}$ and for some s > 0 depending on p. We also provide an application of this new estimate to the hydrodynamic limit of the Boltzmann equation without cutoff. © 2012 Wiley Periodicals, Inc.     

A bijection between Littlewood-Richardson tableaux and rigged configurations

We define a bijection from Littlewood-Richardson tableaux to rigged configurations and show that it preserves the appropriate statistics. This proves in particular a quasi-particle expression for the generalized Kostka polynomials labeled by a partition and a sequence of rectangles R. The generalized Kostka polynomials are q-analogues of multiplicities of the irreducible -module of highest weight in the tensor product .     

The universal covering homomorphism in o‐minimal expansions of groups

Suppose G is a definably connected, definable group in an o‐minimal expansion of an ordered group. We show that the o‐minimal universal covering homomorphism : → G is a locally definable covering homomorphism and π₁(G) is isomorphic to the o‐minimal fundamental group π (G) of G defined using locally definable covering homomorphisms. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Increasing the output length of zero‐error dispersers

Let $\cal{C}$ be a class of probability distributions over a finite set Ω. A function $D : \Omega \mapsto\{0,1\}^{m}$ is a disperser for $\cal{C}$ with entropy threshold $k$ and error $\epsilon$ if for any distribution X in $\cal{C}$ such that X gives positive probability to at least $2^{k}$ elements we have that the distribution $D(X)$ gives positive probability to at least $(1-\epsilon)2^{m}$ elements. A long line of research is devoted to giving explicit (that is polynomial time computable) dispersers (and related objects called “extractors”) for various classes of distributions while trying to maximize m as a function of k. For several interesting classes of distributions there are explicit constructions in the literature of zero‐error dispersers with “small” output length m. In this paper we develop a general technique to improve the output length of zero‐error dispersers. This strategy works for several classes of sources and is inspired by a transformation that improves the output length of extractors (which was given by Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity, (2006) 46–60.) building on earlier work by Gabizon, Raz and Shaltiel (SIAM J Comput 36 (2006) 1072–1094). Our techniques are different than those of Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity (2006) 46–60) and in particular give non‐trivial results in the errorless case. Using our approach we construct improved zero‐error 2‐source dispersers. More precisely, we show that for any constant $\delta >0$ there is a constant $\eta >0$ such that for sufficiently large n there is a poly‐time computable function $D :\{0,1\}^{n}\times\{0,1\}^{n}\mapsto\{0,1\}^{\eta n}$ such that for every two independent distributions $X_1,X_2$ over $\{0,1\}^{n}$ each with support size at least $2^{\delta n}$ , the output distribution $D(X_1,X_2)$ has full support. This improves the output length of previous constructions by Barak, Kindler, Shaltiel, Sudakov and Wigderson (Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) 1–10) and has applications in Ramsey theory and in improved constructions of certain data structures from the work of Fiat and Naor [SIAM J Comput 22 (1993)]. We also use our techniques to give explicit constructions of zero‐error dispersers for bit‐fixing sources and affine sources over polynomially large fields. These constructions improve the best known explicit constructions due to Rao (unpublished data) and Gabizon and Raz [Combinatorica 28 (2008)] and achieve $m=\Omega(k)$ for bit‐fixing sources and $m=k-o(k)$ for affine sources over polynomial size fields. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Weak type (p,q)‐inequalities for the Haar system and differentially subordinated martingales

For any $1\leq p,\,q<\infty$, we determine the optimal constant $C_{p,q}$ such that the following holds. If $(h_k)_{k\geq 0}$ is the Haar system on [0,1], then for any vectors a_k from a separable Hilbert space $\mathcal{H}$ and $\varepsilon_k\in \{-1,1\}$, $k=0,\,1,\,2,\ldots,$ we have This is generalized to the sharp weak‐type inequality where X, Y stand for $\mathcal{H}$‐valued martingales such that Y is differentially subordinate to X.     

The spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups

A ternary quasigroup (or 3‐quasigroup) is a pair (N, q) where N is an n‐set and q(x, y, z) is a ternary operation on N with unique solvability. A 3‐quasigroup is called 2‐idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x)=y. A conjugation of a 3‐quasigroup, considered as an OA(3, 4, n), $({{N}},{\mathcal{B}})$, is a permutation of the coordinate positions applied to the 4‐tuples of ${\mathcal{B}}$. The subgroup of conjugations under which $({{N}},{\mathcal{B}})$ is invariant is called the conjugate invariant subgroup of $({{N}},{\mathcal{B}})$. In this article, we determined the existence of 2‐idempotent 3‐quasigroups of order n, n≡7 or 11 (mod 12) and n≥11, with conjugate invariant subgroup consisting of a single cycle of length three. This result completely determined the spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups. As a corollary, we proved that an overlarge set of Mendelsohn triple system of order n exists if and only if n≡0, 1 (mod 3) and n≠6. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 292–304, 2010     

Well‐posedness in smooth function spaces for moving‐boundary 1‐D compressible euler equations in physical vacuum

The free‐boundary compressible one‐dimensional Euler equations with moving physical vacuum boundary are a system of hyperbolic conservation laws that are both characteristic and degenerate. The physical vacuum singularity (or rate of degeneracy) requires the sound speed $c^2= \gamma \rho^{ \gamma -1}$ to scale as the square root of the distance to the vacuum boundary and has attracted a great deal of attention in recent years. We establish the existence of unique solutions to this system on a short time interval, which are smooth (in Sobolev spaces) all the way to the moving boundary. The proof is founded on a new higher‐order, Hardy‐type inequality in conjunction with an approximation of the Euler equations consisting of a particular degenerate parabolic regularization. Our regular solutions can be viewed as degenerate viscosity solutions. © 2010 Wiley Periodicals, Inc.     

Spectrum of the periodic Dirac operator

The absolute continuity of the spectrum for the periodic Dirac operator

On $ {p} $‐groups of maximal class

Let R be the ring $ {\mathbb Z}[x]/\left({{x^p-1}\over{x-1}}\right) = {\mathbb Z}[\bar{x}] $ and let $ \mathfrak {a} $ be the ideal of R generated by $ (\bar{x}-1) $ . In this paper, we discuss the structure of the $ {\mathbb Z}[C_p] $‐module $ (R/\mathfrak {a}^{n-1}) \wedge (R/\mathfrak {a}^{n-1}) $, which plays an important role in the theory of p‐groups of maximal class (see 2 - 5 ). The generators of this module allow us to obtain the defining relations of some important examples of p‐groups of maximal class with Y₁ of class two. In particular we obtain the best possible estimates for the degree of commutativity of p‐groups of maximal class with Y₁ of class two. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

{2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only

An m‐cycle system (S,C) of order n is said to be {2,3}‐perfect provided each pair of vertices is connected by a path of length 2 in an m‐cycle of C and a path of length 3 in an m‐cycle of C. The class of {2,3}‐perfect m‐cycle systems is said to be equationally defined provided, there exists a variety of quasigroups V with the property that a finite quasigroup (Q, , \, /) belongs to V if and only if its multiplicative (Q, ) part can be constructed from a {2,3}‐perfect m‐cycle system using the 2‐construction (a a = a for all a ∈ Q and if a ≠ b, a b = c and b a = d if and only if the m‐cycle (…, d, x, a, b, y, c, …) ∈ C). The object of this paper is to show that the class of {2,3}‐perfect m‐cycle systems cannot be equationally defined for all m ≥ 10, m ≠ 11. This combined with previous results shows that {2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only. © 2004 Wiley Periodicals, Inc.