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.     

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.     

Chromatic Gallai identities operating on Lovász number

If $G$ is a triangle-free graph, then two Gallai identities can be written as $\alpha (G)+\overline{\chi }(L(G))=|V(G)|=\alpha (L(G))+\overline{\chi }(G)$ , where $\alpha $ and $\overline{\chi }$ denote the stability number and the clique-partition number, and $L(G)$ is the line graph of  $G$ . We show that, surprisingly, both equalities can be preserved for any graph $G$ by deleting the edges of the line graph corresponding to simplicial pairs of adjacent arcs, according to any acyclic orientation of  $G$ . As a consequence, one obtains an operator $\Phi $ which associates to any graph parameter $\beta $ such that $\alpha (G) \le \beta (G) \le \overline{\chi }(G)$ for all graph $G$ , a graph parameter $\Phi _\beta $ such that $\alpha (G) \le \Phi _\beta (G) \le \overline{\chi }(G)$ for all graph $G$ . We prove that $\vartheta (G) \le \Phi _\vartheta (G)$ and that $\Phi _{\overline{\chi }_f}(G)\le \overline{\chi }_f(G)$ for all graph  $G$ , where $\vartheta $ is Lovász theta function and $\overline{\chi }_f$ is the fractional clique-partition number. Moreover, $\overline{\chi }_f(G) \le \Phi _\vartheta (G)$ for triangle-free $G$ . Comparing to the previous strengthenings $\Psi _\vartheta $ and $\vartheta ^{+ \triangle }$ of $\vartheta $ , numerical experiments show that $\Phi _\vartheta $ is a significant better lower bound for $\overline{\chi }$ than $\vartheta $ .     

p-Groups with few conjugacy classes of normalizers

For a group $G$ , denote by $\omega (G)$ the number of conjugacy classes of normalizers of subgroups of $G$ . Clearly, $\omega (G)=1$ if and only if $G$ is a Dedekind group. Hence if $G$ is a 2-group, then $G$ is nilpotent of class $\le 2$ and if $G$ is a $p$ -group, $p>2$ , then $G$ is abelian. We prove a generalization of this. Let $G$ be a finite $p$ -group with $\omega (G)\le p+1$ . If $p=2$ , then $G$ is of class $\le 3$ ; if $p>2$ , then $G$ is of class $\le 2$ .     

Minimal subgroups and the structure of finite groups

A subgroup $H$ of a finite group $G$ is weakly-supplemented in $G$ if there exists a proper subgroup $K$ of $G$ such that $G=HK$ . In this paper we prove that a finite group $G$ is $p$ -nilpotent if every minimal subgroup of $P\bigcap G^{N}$ is weakly-supplemented in $G$ , and when $p=2$ either every cyclic subgroup of $P\bigcap G^{N}$ with order 4 is weakly-supplemented in $G$ or $P$ is quaternion-free, where $p$ is the smallest prime number dividing the order of $G$ , $P$ a sylow $p$ -subgroup of $G$ .     

Subgroup properties of pro-p extensions of centralizers

We prove that a finitely generated pro- $p$ group acting on a pro- $p$ tree $T$ with procyclic edge stabilizers is the fundamental pro- $p$ group of a finite graph of pro- $p$ groups with vertex groups being stabilizers of certain vertices of $T$ and edge groups (when non-trivial) being stabilizers of certain edges of $T$ , in the following two situations: (1) the action is $n$ -acylindrical, i.e., any non-identity element fixes not more than $n$ edges; (2) the group $G$ is generated by its vertex stabilizers. This theorem is applied to obtain several results about pro- $p$ groups from the class $\mathcal L $ defined and studied in Kochloukova and Zalesskii (Math Z 267:109–128, 2011) as pro- $p$ analogues of limit groups. We prove that every pro- $p$ group $G$ from the class $\mathcal L $ is the fundamental pro- $p$ group of a finite graph of pro- $p$ groups with infinite procyclic or trivial edge groups and finitely generated vertex groups; moreover, all non-abelian vertex groups are from the class $\mathcal L $ of lower level than $G$ with respect to the natural hierarchy. This allows us to give an affirmative answer to questions 9.1 and 9.3 in Kochloukova and Zalesskii (Math Z 267:109–128, 2011). Namely, we prove that a group $G$ from the class $\mathcal L $ has Euler–Poincaré characteristic zero if and only if it is abelian, and if every abelian pro- $p$ subgroup of $G$ is procyclic and $G$ itself is not procyclic, then $\mathrm{def}(G)\ge 2$ . Moreover, we prove that $G$ satisfies the Greenberg–Stallings property and any finitely generated non-abelian subgroup of $G$ has finite index in its commensurator.     

Complemented subgroups and the structure of finite groups

Let $p$ be the smallest prime divisor of the order of a finite group $G$ . We examine the structure of $G$ under the hypothesis that $p$ -subgroups of $G$ of certain orders are complemented in $G$ . In particular, we extend some recent results.     

Finite groups all of whose second maximal subgroups are {\mathcal{H }}_p-groups

Let $G$ be a finite group. A subgroup $H$ of $G$ is called an $\mathcal{H }$ -subgroup of $G$ if $N_G(H)\cap H^g\le H$ for all $g\in G$ . A group $G$ is said to be an ${\mathcal{H }}_p$ -group if every cyclic subgroup of $G$ of prime order or order 4 is an $\mathcal{H }$ -subgroup of $G$ . In this paper, the structure of a finite group all of whose second maximal subgroups are ${\mathcal{H }}_p$ -subgroups has been characterized.     

On some primary subgroups and the structure of finite groups

Suppose that $G$ is a finite group and $H$ is a subgroup of $G$ . $H$ is said to be an $s$ -quasinormally embedded in $G$ if for each prime $p$ dividing the order of $H$ , a Sylow $p$ -subgroup of $H$ is also a Sylow $p$ -subgroup of some $S$ -quasinormal subgroup of $G$ ; $H$ is said to be $c$ -normal in $G$ if $G$ has a normal subgroup $T$ such that $G=HT$ and $H\cap T\le H_{G}$ , where $H_{G}$ is the normal core of $H$ in $G$ . We fix in every non-cyclic Sylow subgroup $P$ of $G$ some subgroup $D$ satisfying $1<|D|<|P|$ and study the structure of $G$ under the assumption that every subgroup $H$ of $P$ with $|H|=|D|$ is either $s$ -quasinormally embedded or $c$ -normal in $G$ . Some recent results are generalized and unified.     

On the Degenerate Crossing Number

The degenerate crossing number ${\text{ cr}^{*}}(G)$ of a graph $G$ is the minimum number of crossing points of edges in any drawing of $G$ as a simple topological graph in the plane. This notion was introduced by Pach and Tóth who showed that for a graph $G$ with $n$ vertices and $e \ge 4n$ edges ${\text{ cr}^{*}}(G)=\Omega \big (e^4 / n^4\big )$ . In this paper we completely resolve the main open question about degenerate crossing numbers and show that ${\text{ cr}^{*}}(G)=\Omega \big (e^3 / n^2 \big )$ , provided that $e \ge 4n$ . This bound is best possible (apart for the multiplicative constant) as it matches the tight lower bound for the standard crossing number of a graph.     

On minimal non-M_rC-groups

A group $G$ is said to be a minimax group if it has a finite series whose factors satisfy either the minimal or the maximal condition. Let $D(G)$ denotes the subgroup of $G$ generated by all the Chernikov divisible normal subgroups of $G$ . If $G$ is a soluble-by-finite minimax group and if $D(G)=1$ , then $G$ is said to be a reduced minimax group. Also $G$ is said to be an $ M_{r}C$ -group (respectively, $PC$ -group), if $G/C_{G} \left(x^{G}\right)$ is a reduced minimax (respectively, polycyclic-by-finite) group for all $x\in G$ . These are generalisations of the familiar property of being an $FC$ -group. Finally, if $\mathfrak X $ is a class of groups, then $G$ is said to be a minimal non- $\mathfrak X $ -group if it is not an $\mathfrak X $ -group but all of whose proper subgroups are $\mathfrak X $ -groups. Belyaev and Sesekin characterized minimal non- $FC$ -groups when they have a non-trivial finite or abelian factor group. Here we prove that if $G$ is a group that has a proper subgroup of finite index, then $G$ is a minimal non- $M_{r}C$ -group (respectively, non- $PC$ -group) if, and only if, $G$ is a minimal non- $FC$ -group.     

A new graph parameter related to bounded rank positive semidefinite matrix completions

The Gram dimension $\mathrm{gd}(G)$ of a graph $G$ is the smallest integer $k\ge 1$ such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $G$ , can be completed to a positive semidefinite matrix of rank at most $k$ (assuming a positive semidefinite completion exists). For any fixed $k$ the class of graphs satisfying $\mathrm{gd}(G) \le k$ is minor closed, hence it can be characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $K_{k+1}$ for $k\le 3$ and that there are two minimal forbidden minors: $K_5$ and $K_{2,2,2}$ for $k=4$ . We also show some close connections to Euclidean realizations of graphs and to the graph parameter $\nu ^=(G)$ of van der Holst (Combinatorica 23(4):633–651, 2003). In particular, our characterization of the graphs with $\mathrm{gd}(G)\le 4$ implies the forbidden minor characterization of the 3-realizable graphs of Belk (Discret Comput Geom 37:139–162, 2007) and Belk and Connelly (Discret Comput Geom 37:125–137, 2007) and of the graphs with $\nu ^=(G) \le 4$ of van der Holst (Combinatorica 23(4):633–651, 2003).     

On the signed star domination number of regular multigraphs

Let $G$ be a graph with the vertex set $V(G)$ and the edge set $E(G)$ . A function $f: E(G)\longrightarrow \{-1, 1\}$ is said to be a signed star dominating function of $G$ if $\sum _{e \in E_G(v)}f (e)\ge 1 $ , for every $v \in V(G)$ , where $E_G(v) = \{uv\in E(G)\,|\,u \in V (G)\}$ . The minimum values of $\sum _{e \in E_G(v)}f (e)$ , taken over all signed star dominating functions $f$ on $G$ , is called the signed star domination number of $G$ and denoted by $\gamma _{SS}(G)$ . In this paper we determine the signed star domination number of regular multigraphs.     

Fourier analysis of subgroup conjugacy invariant functions on finite groups

Given a finite group $G$ and a subgroup $H\le G$ , we develop a Fourier analysis for $H$ -conjugacy invariant functions on $G$ , without the assumption that $H$ is a multiplicity-free subgroup of $G$ . We also study the Fourier transform for functions in the center of the algebra of $H$ -conjugacy invariant functions on $G$ . We show that a recent calculation of Cesi is indeed a Fourier transform of a function in the center of the algebra of functions on the symmetric group that are conjugacy invariant with respect to a Young subgroup.     

Characterization of projective linear groups by the order of the normalizer of a Sylow subgroup

Let $r$ be a prime and $G$ be a finite group, and let $R, \,S$ be Sylow $r$ -subgroups of $G$ and $\text{ PGL }(2, r)$ respectively. We prove the following results: (1) If $|G|=|\text{ PGL }(2, r)|$ and $|N_{G}(R)|=|N_{\mathrm{PGL}(2, r)} (S)|$ and $r$ is not a Mersenne prime, then $G$ is isomorphic to $\text{ PSL } (2, r) \times C_{2}, \,\text{ SL }(2, r)$ or $\text{ PGL }(2, r)$ . (2) If $|G|=|\text{ PGL }(2, r)|, \,|N_{G}(R)|=|N_{\mathrm{PGL}(2, r)}(S)|$ where $r>3$ is a Mersenne prime and $r$ is an isolated vertex of the prime graph of $G$ , then $G\cong \text{ PGL }(2, r)$ .     

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

On S-permutably embedded subgroups of finite groups

A subgroup $A$ of a finite group $G$ is said to be $S$ -permutably embedded in $G$ if for each prime $p$ dividing the order of $A$ , every Sylow $p$ -subgroup of $A$ is a Sylow $p$ -subgroup of some $S$ -permutable subgroup of $G$ . In this paper we determine how the $S$ -permutable embedding of several families of subgroups of a finite group influences its structure.     

On cyclic fixed points of spectra

For a finite $p$ -group $G$ and a bounded below $G$ -spectrum $X$ of finite type mod  $p$ , the $G$ -equivariant Segal conjecture for $X$ asserts that the canonical map $X^G \rightarrow X^{hG}$ , from $G$ -fixed points to $G$ -homotopy fixed points, is a $p$ -adic equivalence. Let $C_{p^n}$ be the cyclic group of order  $p^n$ . We show that if the $C_p$ -equivariant Segal conjecture holds for a $C_{p^n}$ -spectrum $X$ , as well as for each of its geometric fixed point spectra $\varPhi ^{C_{p^e}}(X)$ for $0 < e < n$ , then the $C_{p^n}$ -equivariant Segal conjecture holds for  $X$ . Similar results also hold for weaker forms of the Segal conjecture, asking only that the canonical map induces an equivalence in sufficiently high degrees, on homotopy groups with suitable finite coefficients.     

Asymptotics for Hessenberg Matrices for the Bergman Shift Operator on Jordan Regions

Let $G$ be a bounded Jordan domain in the complex plane. The Bergman polynomials $\{p_n\}_{n=0}^\infty $ of $G$ are the orthonormal polynomials with respect to the area measure over $G$ . They are uniquely defined by the entries of an infinite upper Hessenberg matrix $M$ . This matrix represents the Bergman shift operator of $G$ . The main purpose of the paper is to describe and analyze a close relation between $M$ and the Toeplitz matrix with symbol the normalized conformal map of the exterior of the unit circle onto the complement of $\overline{G}$ . Our results are based on the strong asymptotics of $p_n$ . As an application, we describe and analyze an algorithm for recovering the shape of $G$ from its area moments.