Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

Which finite simple groups are unit groups?

We prove that if G$G$ is a finite simple group which is the unit group of a ring, then G$G$ is isomorphic to: (a) a cyclic group of order 2; or (b) a cyclic group of prime order 2^k−1$2^k-1$ for some k$k$; or (c) a projective special linear group _PSLn(_F2)${PSL}_n\left({\mathbb{F}}_2\right)$ for some n≥3$n\ge 3$. Moreover, these groups do all occur as unit groups. We deduce this classification from a more general result, which holds for groups G$G$ with no non-trivial normal 2-subgroup.     

Parametric inference for discretely observed multidimensional diffusions with small diffusion coefficient

We consider a multidimensional diffusion X$X$ with drift coefficient b(α,_Xt)$b(\alpha ,X_t)$ and diffusion coefficient ?σ(β,_Xt)$?\sigma (\beta ,X_t)$. The diffusion sample path is discretely observed at times _tk=kΔ$t_k=k\Delta$ for k=1…n$k=1\dots n$ on a fixed interval [0,T]$[0,T]$. We study minimum contrast estimators derived from the Gaussian process approximating X$X$ for small ?$?$. We obtain consistent and asymptotically normal estimators of α$\alpha$ for fixed Δ$\Delta$ and ?→0$?\to 0$ and of (α,β)$(\alpha ,\beta )$ for Δ→0$\Delta \to 0$ and ?→0$?\to 0$ without any condition linking ?$?$ and Δ$\Delta$. We compare the estimators obtained with various methods and for various magnitudes of Δ$\Delta$ and ?$?$ based on simulation studies. Finally, we investigate the interest of using such methods in an epidemiological framework.     

Disjoint paths in tournaments

Given k   pairs of vertices (_si,_ti)$(s_i,t_i)$(1≤i≤k)$(1\le i\le k)$ of a digraph G, how can we test whether there exist k   vertex-disjoint directed paths from _si$s_i$ to _ti$t_i$ for 1≤i≤k$1\le i\le k$? This is NP-complete in general digraphs, even for k=2$k=2$ [2], but for k=2$k=2$ there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.     

An upper bound for a valence of a face in a parallelohedral tiling

Consider a face-to-face parallelohedral tiling of R^d${\mathbb{R}}^d$ and a (d−k)$(d-k)$-dimensional face F$F$ of the tiling. We prove that the valence of F$F$ (i.e. the number of tiles containing F$F$ as a face) is not greater than 2^k$2^k$. If the tiling is affinely equivalent to a Voronoi tiling for some lattice (the so called Voronoi case), this gives a well-known upper bound for the number of vertices of a Delaunay k$k$-cell. Yet we emphasize that such an affine equivalence is not assumed in the proof.     

Embedding cycles of given length in oriented graphs

Kelly, Kühn and Osthus conjectured that for any ?≥4$?\ge 4$ and the smallest number k≥3$k\ge 3$ that does not divide ?$?$, any large enough oriented graph G$G$ with δ⁺(G),δ⁻(G)≥⌊|V(G)|/k⌋+1${\delta }^{+}\left(G\right),{\delta }^{-}\left(G\right)\ge \lfloor \left|V\left(G\right)\right|/k\rfloor +1$ contains a directed cycle of length ?$?$. We prove this conjecture asymptotically for the case when ?$?$ is large enough compared to k$k$ and k≥7$k\ge 7$. The case when k≤6$k\le 6$ was already settled asymptotically by Kelly, Kühn and Osthus.     

Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs

We say that a hypergraph H$H$ is hamiltonian chain saturated if H$H$ does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H$H$. In this paper, for each k≥3$k\ge 3$, we establish the right order of magnitude n^k−1$n^{k-1}$ for the size of the smallest k$k$-uniform hamiltonian chain saturated hypergraph. This solves an open problem of G.Y. Katona.     

[1, 2]-sets in graphs

A subset S⊆V$S\subseteq V$ in a graph G=(V,E)$G=(V,E)$ is a [j,k]$[j,k]$-set if, for every vertex v∈V?S$v\in V?S$, j≤|N(v)∩S|≤k$j\le |N\left(v\right)\cap S|\le k$ for non-negative integers j$j$ and k$k$, that is, every vertex v∈V?S$v\in V?S$ is adjacent to at least j$j$ but not more than k$k$ vertices in S$S$. In this paper, we focus on small j$j$ and k$k$, and relate the concept of [j,k]$[j,k]$-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k$k$-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G$G$, the restrained domination number is equal to the domination number of G$G$.     

Feedback vertex set on graphs of low clique-width

The Feedback Vertex Set problem asks whether a graph contains q$q$ vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q$q$ vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph G$G$ of clique-width cw$cw$ and a cw$cw$-expression of G$G$, we solve the Minimum Feedback Vertex Set problem in time O(n²2^O(cwlogcw))$O\left(n^2{2}^{O(cwlogcw)}\right)$. Our algorithm applies dynamic programming on a so-called k$k$-module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from ak$k$-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

Limit laws for UGROW random graphs

Representations are found for a limit law L(Z(k,p))$L\left(Z(k,p)\right)$ obtained from an expanding sequence of random forests containing n$n$ nodes with p∈(0,1]$p\in (0,1]$ a probability controlling bond formation. One implies that Z(k,p)$Z(k,p)$ is stochastically decreasing as k$k$ increases and that norming gives an exponential limit law. Limit theorems are given for the order of component trees. The proofs exploit properties of the gamma function.     

Derivations and local derivations on Freudenthal almost f-algebras

Let A be an Archimedean f  -algebra and let N(A)$N(A)$ be the set of all nilpotent elements of A. Colville et al. [4] proved that a positive linear map d:A→A$d:A\to A$ is a derivation if and only if d(A)⊂N(A)$d(A)\subset N(A)$ and d(A²)={0}$d(A^2)=\{0\}$, where A²$A^2$ is the set of all products ab in A.     

On the norming constants for normal maxima

Given n   independent standard normal random variables, it is well known that their maxima _Mn$M_n$ can be normalized such that their distribution converges to the Gumbel law. In a remarkable study, Hall proved that the Kolmogorov distance _dn$d_n$ between the normalized _Mn$M_n$ and its associated limit distribution is less than 3/log?n$3/\log ?n$. In the present study, we propose a different set of norming constants that allow this upper bound to be decreased with _dn≤C(m)/log?n$d_n\le C(m)/\log ?n$ for n≥m≥5$n\ge m\ge 5$. Furthermore, the function C(m)$C(m)$ is computed explicitly, which satisfies C(m)≤1$C(m)\le 1$ and _limm→∞?C(m)=1/3${\lim }_{m\to \infty }?C(m)=1/3$. As a consequence, some new and effective norming constants are provided using the asymptotic expansion of a Lambert W type function.