Nonvanishing of Kronecker coefficients for rectangular shapes

We prove that for any partition (λ₁,…,λd²) of size ?d there exists k?1 such that the tensor square of the irreducible representation of the symmetric group Sk?d with respect to the rectangular partition (k?,…,k?) contains the irreducible representation corresponding to the stretched partition (kλ₁,…,kλd²). We also prove a related approximate version of this statement in which the stretching factor k is effectively bounded in terms of d. We further discuss the consequences for geometric complexity theory which provided the motivation for this work.     

Local solutions for a coupled system of Kirchhoff type

We investigate the existence of local solutions of the following coupled system of Kirchhoff equations subject to nonlinear dissipation on the boundary: (∗) Here {Γ₀,Γ₁} is an appropriate partition of the boundary Γ of Ω and ν(x), the outer unit normal vector at x∈Γ₁.By applying the Galerkin method with a special basis for the space where lie the approximations of the initial data, we obtain local solutions of the initial-boundary value problem for (∗).     

Complete partitions of graphs

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime(n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form Θ((lgn) ^c ) for some constant c strictly between 0 and 1. The work reported here is a merger of the results reported in [30] and [21].     

Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

On the number of groups in clustering

Clustering is the problem of partitioning data into a finite number k of homogeneous and separate groups, called clusters. A good choice of k is essential for building meaningful clusters. In this paper, this task is addressed from the point of view of model selection via penalization. We design an appropriate penalty shape and derive an associated oracle-type inequality. The method is illustrated on both simulated and real-life data sets.     

Integrability of a nuclear spin generator

In this work we consider a nuclear spin generator given by where α, β, κ are nonnegative parameters. It models the two temperature feedback nuclear reactor problem as model by Vreeke and Sandquist (1970) [4]. We contribute to the understanding of its global dynamics, or more precisely, to the topological structure of its orbits by studying the integrability problem. We prove that β=0 or β≠0 and κ=0 are the only values of the parameters for which the system is integrable, and in this case we provide an explicit expression for its first integrals.     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.     

Optimal inverse Littlewood–Offord theorems

Let ηi, i=1,…,n, be iid Bernoulli random variables, taking values ±1 with probability . Given a multiset V of n integers v₁,…,vn, we define the concentration probability as A classical result of Littlewood–Offord and Erd?s from the 1940s asserts that, if the vi are non-zero, then ρ(V) is O(n−1/2). Since then, many researchers have obtained improved bounds by assuming various extra restrictions on V.About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the inverse Littlewood–Offord problem. In the inverse problem, one would like to characterize the set V, given that ρ(V) is relatively large.In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen the previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sárközy and Szemerédi and Halász.The method also applies to the continuous setting and leads to a simple proof for the β-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices.All results extend to the general case when V is a subset of an abelian torsion-free group, and ηi are independent variables satisfying some weak conditions.     

Harnack inequalities for Yamabe type equations

We give some a priori estimates of type sup×inf on Riemannian manifolds for Yamabe and prescribed curvature type equations. An application of those results is the uniqueness result for Δu+?u=uN−1 with ? small enough.     

Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u⁴n) and the p-partition problem can be solved in time O(p²u⁴n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.     

The homotopy limit problem for Hermitian K-theory, equivariant motivic homotopy theory and motivic Real cobordism

The homotopy limit problem for Karoubi?s Hermitian K-theory (Karoubi, 1980) [26] was posed by Thomason (1983) [44]. There is a canonical map from algebraic Hermitian K-theory to the Z/2-homotopy fixed points of algebraic K-theory. The problem asks, roughly, how close this map is to being an isomorphism, specifically after completion at 2. In this paper, we solve this problem completely for fields of characteristic 0 (Theorems 16, 20). We show that the 2-completed map is an isomorphism for fields F of characteristic 0 which satisfy cd₂(F[i])<∞, but not in general.     

Global uniqueness and reconstruction for the multi-channel Gel?fand–Calderón inverse problem in two dimensions

We study the multi-channel Gel?fand–Calderón inverse problem in two dimensions, i.e. the inverse boundary value problem for the equation −Δψ+v(x)ψ=0, x∈D, where v is a smooth matrix-valued potential defined on a bounded planar domain D. We give an exact global reconstruction method for finding v from the associated Dirichlet-to-Neumann operator. This also yields a global uniqueness results: if two smooth matrix-valued potentials defined on a bounded planar domain have the same Dirichlet-to-Neumann operator then they coincide.     

Dubrovin's duality for F-manifolds with eventual identities

A vector field E on an F-manifold (M,°,e) is an eventual identity if it is invertible and the multiplication X?Y:=X°Y°E−1 defines a new F-manifold structure on M. We give a characterization of such eventual identities, this being a problem raised by Manin (2005) [12]. We develop a duality between F-manifolds with eventual identities and we show that this duality is compatible with the local irreducible decomposition of F-manifolds and preserves the class of Riemannian F-manifolds. We find necessary and sufficient conditions on the eventual identity which ensure that the classes of harmonic Higgs bundles, DChk-structures and weak CV-structures are preserved by our duality. Examples of such structures are given in the case of a semi-simple multiplication. We use eventual identities to construct compatible pairs of metrics.     

On open problems concerning distributional chaos for triangular maps

We show that in the class T of the triangular maps (x,y)?(f(x),g_x(y)) of the square there is a map of type 2^∞ with non-minimal recurrent points which is not DC3. We also show that every DC1 continuous map of a compact metric space has a trajectory which cannot be (weakly) approximated by trajectories of compact periodic sets. These two results make possible to answer some open questions concerning classification of maps in T with zero topological entropy, and contribute to an old problem formulated by A.N. Sharkovsky.     

On linear and nonlinear fourth-order eigenvalue problems with indefinite weight

We determine the principal eigenvalues of the linear indefinite weight problem Moreover, we investigate the existence of positive solutions for the corresponding nonlinear indefinite weight problem, where g:[0,1]→R is a continuous function which attains both positive and negative values, f∈C(R,R), and r is a parameter.     

Finding Skew Partitions Efficiently

A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts A, B, C, D such that there are all possible edges between A and B and no edges between C and D. We present a polynomial-time algorithm for testing whether a graph admits a skew partition. Our algorithm solves the more general list skew partition problem, where the input contains, for each vertex, a list containing some of the labels A, B, C, D of the four parts. Our polynomial-time algorithm settles the complexity of the original partition problem proposed by Chvátal in 1985 and answers a recent question of Feder, Hell, Klein, and Motwani.     

The relative Picard functor on schemes over a symmetric monoidal category

We consider schemes (X,OX) over an abelian closed symmetric monoidal category (C,⊗,1). Our aim is to extend a theorem of Kleiman on the relative Picard functor to schemes over (C,⊗,1). For this purpose, we also develop some basic theory on quasi-coherent modules on schemes (X,OX) over C.     

The hyperbolic mean curvature flow

We introduce a geometric evolution equation of hyperbolic type, which governs the evolution of a hypersurface moving in the direction of its mean curvature vector. The flow stems from a geometrically natural action containing kinetic and internal energy terms. As the mean curvature of the hypersurface is the main driving factor, we refer to this model as the hyperbolic mean curvature flow (HMCF). The case that the initial velocity field is normal to the hypersurface is of particular interest: this property is preserved during the evolution and gives rise to a comparatively simpler evolution equation. We also consider the case where the manifold can be viewed as a graph over a fixed manifold. Our main results are as follows. First, we derive several balance laws satisfied by the hypersurface during the evolution. Second, we establish that the initial-value problem is locally well-posed in Sobolev spaces; this is achieved by exhibiting a convexity property satisfied by the energy density which is naturally associated with the flow. Third, we provide some criteria ensuring that the flow will blow-up in finite time. Fourth, in the case of graphs, we introduce a concept of weak solutions suitably restricted by an entropy inequality, and we prove that a classical solution is unique in the larger class of entropy solutions. In the special case of one-dimensional graphs, a global-in-time existence result is established.     

On special types of nonholonomic contact elements

Our starting point has been a recent clarification of the role of semiholonomic contact elements in the theory of submanifolds of Cartan geometries, Kolá? and Vitolo (2010) [5]. We deduce some further properties of the iterated contact elements by using the general concept of contact (n,F)-element for a regular subcategory F of the category of nonholonomic r-jets. Special attention is paid to the incidence relation of contact F-elements of different dimensions.     

Remark on the global existence and large time asymptotics of solutions for the quadratic NLS

We study the global in time existence of small solutions to the nonlinear Schrödinger equation with quadratic interactions (0.1) We prove that if the initial data u₀ satisfy smallness conditions in the weighted Sobolev norm, then the solution of the Cauchy problem (0.1) exists globally in time. Furthermore, we prove the existence of the usual scattering states and find the large time asymptotics of the solutions.