Convex optimization for the planted k-disjoint-clique problem

We consider the $k$ -disjoint-clique problem. The input is an undirected graph $G$ in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph $k$ disjoint cliques that cover the maximum number of nodes of $G$ . This problem may be understood as a general way to pose the classical ‘clustering’ problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows ‘noise’ nodes to be present in the input data that are not part of any of the cliques. The $k$ -disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of $k$ disjoint large cliques (called ‘planted cliques’) that are then obscured by noise edges inserted either at random or by an adversary, as well as additional nodes not belonging to any of the $k$ planted cliques.     

Free subalgebras of division algebras over uncountable fields

We study the existence of free subalgebras in division algebras, and prove the following general result: if $A$ is a noetherian domain which is countably generated over an uncountable algebraically closed field $k$ of characteristic $0$ , then either the quotient division algebra of $A$ contains a free algebra on two generators, or it is left algebraic over every maximal subfield. As an application, we prove that if $k$ is an uncountable algebraically closed field and $A$ is a finitely generated $k$ -algebra that is a domain of GK-dimension strictly less than $3$ , then either $A$ satisfies a polynomial identity, or the quotient division algebra of $A$ contains a free $k$ -algebra on two generators.     

Highly Incident Configurations with Chiral Symmetry

A geometric $k$ -configuration is a collection of points and straight lines in the plane so that $k$ points lie on each line and $k$ lines pass through this point. We introduce a new construction method for constructing $k$ -configurations with non-trivial dihedral or chiral (i.e., purely rotational) symmetry, for any $k \ge 3$ ; the configurations produced have $2^{k-2}$ symmetry classes of points and lines. The construction method produces the only known infinite class of symmetric geometric 7-configurations, the second known infinite class of symmetric geometric 6-configurations, and the only known 6-configurations with chiral symmetry.     

Counting nonsingular matrices with primitive row vectors

We give an asymptotic expression for the number of nonsingular integer $n\times n$ -matrices with primitive row vectors, determinant $k$ , and Euclidean matrix norm less than $T$ , as $T\rightarrow \infty $ . We also investigate the density of matrices with primitive rows in the space of matrices with determinant $k$ , and determine its asymptotics for large $k$ .     

An Index Formula in Connection with Meromorphic Approximation

Let $\Phi $ be a continuous $n\times n$ matrix-valued function on the unit circle $\mathbb T $ such that the $(k-1)$ st singular value of the Hankel operator with symbol $\Phi $ is greater than the $k$ th singular value. In this case, it is well-known that $\Phi $ has a unique superoptimal meromorphic approximant $Q$ in $H^{\infty }_{(k)}$ ; that is, $Q$ has at most $k$ poles in the unit disc $\mathbb D $ (in the sense that the McMillan degree of $Q$ in $\mathbb D $ is at most $k$ ) and $Q$ minimizes the essential suprema of singular values $s_{j}\left((\Phi -Q)(\zeta )\right)\!, j\ge 0$ , with respect to the lexicographic ordering. For each $j\ge 0$ , the essential supremum of $s_{j}\left((\Phi -Q)(\zeta )\right)$ is called the $j$ th superoptimal singular value of degree $k$ of $\Phi $ . We prove that if $\Phi $ has $n$ non-zero superoptimal singular values of degree $k$ , then the Toeplitz operator $T_{\Phi -Q}$ with symbol $\Phi -Q$ is Fredholm and has index $$ \mathrm{ind}T_{\Phi -Q}=\dim \ker T_{\Phi -Q}=2k+\dim \mathcal E , $$ where $\mathcal E =\{ \xi \in \ker H_{Q}: \Vert H_{\Phi }\xi \Vert _{2}=\Vert (\Phi -Q)\xi \Vert _{2}\}$ and $H_{\Phi }$ denotes the Hankel operator with symbol $\Phi $ . This result can in fact be extended from continuous matrix-valued functions to the wider class of $k$ -admissible matrix-valued functions, i.e. essentially bounded $n\times n$ matrix-valued functions $\Phi $ on $\mathbb T $ for which the essential norm of the Hankel operator $H_{\Phi }$ is strictly less than the smallest non-zero superoptimal singular value of degree $k$ of $\Phi $ .     

Approximation algorithms for k-partitioning problems with partition matroid constraint

The $k$ -partitioning problem with partition matroid constraint is to partition the union of $k$ given sets of size $m$ into $m$ sets such that each set contains exactly one element from each given set. With the objective of minimizing the maximum load, we present an efficient polynomial time approximation scheme (EPTAS) for the case where $k$ is a constant and a full polynomial time approximation scheme (FPTAS) for the case where $m$ is a constant; with the objective of maximizing the minimum load, we present a $\frac{1}{k-1}$ -approximation algorithm for the general case, an EPTAS for the case where $k$ is a constant; with the objective of minimizing the $l_p$ -norm of the load vector, we prove that the layered LPT algorithm (Wu and Yao in Theor Comput Sci 374:41–48, 2007) is an all-norm 2-approximation algorithm.     

Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem

We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order $n$ . Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by $k$ -opt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations.     

Integer-valued polynomials over matrices and divided differences

Let $D$ be an integrally closed domain with quotient field $K$ and $n$ a positive integer. We give a characterization of the polynomials in $K[X]$ which are integer-valued over the set of matrices $M_n(D)$ in terms of their divided differences. A necessary and sufficient condition on $f\in K[X]$ to be integer-valued over $M_n(D)$ is that, for each $k$ less than $n$ , the $k$ th divided difference of $f$ is integral-valued on every subset of the roots of any monic polynomial over $D$ of degree $n$ . If in addition $D$ has zero Jacobson radical then it is sufficient to check the above conditions on subsets of the roots of monic irreducible polynomials of degree $n$ , that is, conjugate integral elements of degree $n$ over $D$ .     

Variance asymptotics for random polytopes in smooth convex bodies

Let $K \subset \mathbb R ^d$ be a smooth convex set and let $\mathcal{P }_{\lambda }$ be a Poisson point process on $\mathbb R ^d$ of intensity ${\lambda }$ . The convex hull of $\mathcal{P }_{\lambda }\cap K$ is a random convex polytope $K_{\lambda }$ . As ${\lambda }\rightarrow \infty $ , we show that the variance of the number of $k$ -dimensional faces of $K_{\lambda }$ , when properly scaled, converges to a scalar multiple of the affine surface area of $K$ . Similar asymptotics hold for the variance of the number of $k$ -dimensional faces for the convex hull of a binomial process in $K$ .     

Join the shortest queue among k parallel queues: tail asymptotics of its stationary distribution

We are concerned with an $M/M$ -type join the shortest queue ( $M/M$ -JSQ for short) with $k$ parallel queues for an arbitrary positive integer $k$ , where the servers may be heterogeneous. We are interested in the tail asymptotic of the stationary distribution of this queueing model, provided the system is stable. We prove that this asymptotic for the minimum queue length is exactly geometric, and its decay rate is the $k$ th power of the traffic intensity of the corresponding $k$ server queues with a single waiting line. For this, we use two formulations, a quasi-birth-and-death (QBD for short) process and a reflecting random walk on the boundary of the $k+1$ -dimensional orthant. The QBD process is typically used in the literature for studying the JSQ with two parallel queues, but the random walk also plays a key roll in our arguments, which enables us to use the existing results on tail asymptotics for the QBD process.     

Polytopal Affine Semigroups with Holes Deep Inside

Given a positive integer $k$ k , we construct a lattice $3$ 3 -simplex $P$ P with the following property: The affine semigroup $Q_P$ Q P associated to $P$ P is not normal, and every element $q \in \overline{Q}_P \setminus Q_P$ q ∈ Q ¯ P ? Q P has lattice distance at least $k$ k above every facet of $Q_P$ Q P .     

Nearby motives and motivic nearby cycles

We prove that the construction of motivic nearby cycles, introduced by Jan Denef and François Loeser, is compatible with the formalism of nearby motives, developed by Joseph Ayoub. Let $k$ be an arbitrary field of characteristic zero, and let $X$ be a smooth quasi-projective $k$ -scheme. Precisely, we show that, in the Grothendieck group of constructible étale motives, the image of the nearby motive associated with a flat morphism of $k$ -schemes $f:X\rightarrow \mathbb A ^1_k$ , in the sense of Ayoub’s theory, can be identified with the image of Denef and Loeser’s motivic nearby cycles associated with $f$ . In particular, it provides a realization of the motivic Milnor fiber of $f$ in the “non-virtual” motivic world.     

Max-min weight balanced connected partition

For a connected graph $G=(V,E)$ and a positive integral vertex weight function $w$ , a max-min weight balanced connected $k$ -partition of $G$ , denoted as $BCP_k$ , is a partition of $V$ into $k$ disjoint vertex subsets $(V_1,V_2,\ldots ,V_k)$ such that each $G[V_i]$ (the subgraph of $G$ induced by $V_i$ ) is connected, and $\min _{1\le i\le k}\{w(V_i)\}$ is maximum. Such a problem has a lot of applications in image processing and clustering, and was proved to be NP-hard. In this paper, we study $BCP_k$ on a special class of graphs: trapezoid graphs whose maximum degree is bounded by a constant. A pseudo-polynomial time algorithm is given, based on which an FPTAS is obtained for $k=2,3,4$ . A step-stone for the analysis of the FPTAS depends on a lower bound for the optimal value of $BCP_k$ in terms of the total weight of the graph. In providing such a lower bound, a byproduct of this paper is that any 4-connected trapezoid graph on at least seven vertices has a 4-contractible edge, which may have a value in its own right.     

Many Collinear k-Tuples with no k+1 Collinear Points

For every $k>3$ k > 3 , we give a construction of planar point sets with many collinear $k$ k -tuples and no collinear $(k+1)$ ( k + 1 ) -tuples. We show that there are $n_0=n_0(k)$ n 0 = n 0 ( k ) and $c=c(k)$ c = c ( k ) such that if $n\ge n_0$ n ≥ n 0 , then there exists a set of $n$ n points in the plane that does not contain $k+1$ k + 1 points on a line, but it contains at least $n^{2-({c}/{\sqrt{\log n}})}$ n 2 - ( c / log n ) collinear $k$ k -tuples of points. Thus, we significantly improve the previously best known lower bound for the largest number of collinear $k$ k -tuples in such a set, and get reasonably close to the trivial upper bound $O(n^2)$ O ( n 2 ) .     

Integer valued polynomials on lower triangular integer matrices

Let $D$ be an integral domain with quotient field $K$ . In this paper we study the algebra of polynomials in $K[x]$ which map the set of lower triangular $n\times n$ matrices with coefficients in $D$ into itself and show that it coincides with the algebra of polynomials whose divided differences of order $k$ map $D^{k+1}$ into $D$ for every $k< n$ . Using this result we describe the polynomial closure of this set of matrices when $D$ is the ring of integers in a global field.     

Partial regularity at the first singular time for hypersurfaces evolving by mean curvature

In this paper, we consider smooth, properly immersed hypersurfaces evolving by mean curvature in some open subset of   $\mathbb R ^{n+1}$ on a time interval $(0, t_0)$ . We prove that $p$ -integrability with $p\ge 2$ for the second fundamental form of these hypersurfaces in some space–time region $B_R(y)\times (0, t_0)$ implies that the $\mathcal H ^{n+2-p}$ -measure of the first singular set vanishes inside $B_R(y)$ . For $p=2$ and $n=2$ , this was established by Han and Sun. Our result furthermore generalizes previous work of Xu, Ye and Zhao and of Le and Sesum for $p\ge n+2$ , in which case the singular set was shown to be empty. By a theorem of Ilmanen, our integrability condition is satisfied for $p=2$ and $n=2\,$ if the initial surface has finite genus. Thus, the first singular set has zero $\mathcal H ^2$ -measure in this case. This is the conclusion of Brakke’s main regularity theorem for the special case of surfaces, but derived without having to impose the area continuity and unit density hypothesis. It follows from recent work of Head and of Huisken and Sinestrari that for the flow of closed, $k$ -convex hypersurfaces, that is hypersurfaces whose sum of the smallest $k$ principal curvatures is positive, our integrability criterion holds with exponent $p=n+3-k-\alpha $ for all small $\alpha >0$ as long as $1\le k\le n-1$ . Therefore, the first singular set of such solutions is at most $(k-1)$ -dimensional, which is an optimal estimate in view of some explicit examples.     

On adding a variable to a Frobenius manifold and generalizations

Let $\pi :V\rightarrow M$ be a (real or holomorphic) vector bundle whose base has an almost Frobenius structure $(\circ _{M},e_{M},g_{M})$ and typical fiber has the structure of a Frobenius algebra $(\circ _{V},e_{V},g_{V})$ . Using a connection $D$ on the bundle $\pi : V{\,\rightarrow \,}M$ and a morphism $\alpha :V\rightarrow TM$ , we construct an almost Frobenius structure $(\circ , e_{V},g)$ on the manifold $V$ and we study when it is Frobenius. In particular, we describe all (real) positive definite Frobenius structures on $V$ obtained in this way, when $M$ is a semisimple Frobenius manifold with non-vanishing rotation coefficients. In the holomorphic setting, we add a real structure $k_{M}$ on $M$ and a real structure $k_{V}$ on the bundle $\pi : V \rightarrow M$ . Using $k_{M}$ , $k_{V}$ and $D$ we define a real structure $k$ on the manifold $V$ . We study when $k$ , together with an almost Frobenius structure $(\circ , e_{V}, g) $ , satisfies the tt*- equations. Along the way, we prove various properties of adding variables to a Frobenius manifold, in connection with Legendre transformations and $tt^{*}$ -geometry.     

Generalized derivations with annihilating and centralizing Engel conditions on Lie ideals

Let $R$ be a non-commutative prime ring, with center $Z(R)$ , extended centroid $C$ and let $F$ be a non-zero generalized derivation of $R$ . Denote by $L$ a non-central Lie ideal of $R$ . If there exists $0\ne a\in R$ such that $a[F(x),x]_k\in Z(R)$ for all $x\in L$ , where $k$ is a fixed integer, then one of the followings holds: (1) either there exists $\lambda \in C$ such that $F(x)=\lambda x$ for all $x\in R$ , (2) or $R$ satisfies $s_4$ , the standard identity in $4$ variables, and $char(R)=2$ ; (3) or $R$ satisfies $s_4$ and there exist $q\in U, \gamma \in C$ such that $F(x)=qx+xq+\gamma x$ .     

Elliptic equations with jumping nonlinearities involving high eigenvalues

We present some multiplicity results concerning semilinear elliptic Dirichlet problems with jumping nonlinearities where the jumping condition involves a set of high eigenvalues not including the first one. Using a variational method we show that the number of solutions may be arbitrarily large provided the number of jumped eigenvalues is large enough. Indeed, we prove that for every positive integer $k$ there exists a positive integer $n(k)$ such that, if the number of jumped eigenvalues is greater than $n(k),$ then the problem has at least a solution which presents $k$ peaks. Moreover, we describe the asymptotic behaviour of the solutions as the number of jumped eigenvalues tends to infinity; in particular, we analyse some concentration phenomena of the peaks (near points or suitable manifolds), we describe the asymptotic profile of the rescaled peaks, etc $\ldots $