Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If \(\mathcal {M}\) is a matroid over a set of elements S with independent set \(\mathcal {I}\), and \(m=|S|\), we suppose that we are given an oracle function that takes an independent set \(A\in \mathcal {I}\) and an element \(e\in S\) and determines if \(A\cup \{e\}\) is independent in time I(m). Also, given that the elements of A are represented in an ordered way \(A=\{A_1,\dots ,A_k\}\), we denote the time to check if \(A\cup \{e\}\notin \mathcal {I}\) and if so, to find the minimum \(i\in \{0,\dots ,k\}\) such that \(\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}\) by \(I^*(m)\). Then, we describe a new FPTAS that computes for any \(\varepsilon >0\) and for any matroid \(\mathcal {M}\) of rank r over a set S of m elements, in memory space O(m), the packing \(\varLambda ({\mathcal {M}})\) within \(1+\varepsilon \) in time \(O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)\), and the covering \(\varUpsilon ({\mathcal {M}})\) in time \(O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)\). This method outperforms in time complexity by a factor of \(\varOmega (m/r)\) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of \(\varOmega (m)\) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.     

Generating Hyperbolic Singularities in Semitoric Systems Via Hopf Bifurcations

Let \((M,\Omega )\) be a connected symplectic 4-manifold and let \(F=(J,H) :M\rightarrow \mathbb {R}^2\) be a completely integrable system on M with only non-degenerate singularities. Assume that F does not have singularities with hyperbolic blocks and that \(p_1,\ldots ,p_n\) are the focus–focus singularities of F. For each subset \(S=\{i_1,\ldots ,i_j\}\), we will show how to modify F locally around any \(p_i, i \in S\), in order to create a new integrable system \(\widetilde{F}=(J, \widetilde{H}) :M \rightarrow \mathbb {R}^2\) such that its classical spectrum \(\widetilde{F}(M)\) contains j smooth curves of singular values corresponding to non-degenerate transversally hyperbolic singularities of \(\widetilde{F}\). Moreover the focus–focus singularities of \(\widetilde{F}\) are precisely \(p_i\), \(i \in \{1,\ldots ,n\} \setminus S\). The proof is based on Eliasson’s linearization theorem for non-degenerate singularities, and properties of the Hamiltonian Hopf bifurcation.     

A spectral-like decomposition for transitive Anosov flows in dimension three

Given a (transitive or non-transitive) Anosov vector field X on a closed three dimensional manifold M, one may try to decompose (M, X) by cutting M along tori and Klein bottles transverse to X. We prove that one can find a finite collection \(\{S_1,\dots ,S_n\}\) of pairwise disjoint, pairwise non-parallel tori and Klein bottles transverse to X, such that the maximal invariant sets \(\Lambda _1,\dots ,\Lambda _m\) of the connected components \(V_1,\dots ,V_m\) of \(M-(S_1\cup \dots \cup S_n)\) satisfy the following properties:

• each \(\Lambda _i\) is a compact invariant locally maximal transitive set for X;
• the collection \(\{\Lambda _1,\dots ,\Lambda _m\}\) is canonically attached to the pair (M, X) (i.e. it can be defined independently of the collection of tori and Klein bottles \(\{S_1,\dots ,S_n\}\));
• the \(\Lambda _i\)’s are the smallest possible: for every (possibly infinite) collection \(\{S_i\}_{i\in I}\) of tori and Klein bottles transverse to X, the \(\Lambda _i\)’s are contained in the maximal invariant set of \(M-\cup _i S_i\).

To a certain extent, the sets \(\Lambda _1,\dots ,\Lambda _m\) are analogs (for Anosov vector field in dimension 3) of the basic pieces which appear in the spectral decomposition of a non-transitive axiom A vector field. Then we discuss the uniqueness of such a decomposition: we prove that the pieces of the decomposition \(V_1,\dots ,V_m\), equipped with the restriction of the Anosov vector field X, are “almost unique up to topological equivalence”.

     

Brownian Paths Homogeneously Distributed in Space: Percolation Phase Transition and Uniqueness of the Unbounded Cluster

We consider a continuum percolation model on \(\mathbb {R}^d\), \(d\ge 1\). For \(t,\lambda \in (0,\infty )\) and \(d\in \{1,2,3\}\), the occupied set is given by the union of independent Brownian paths running up to time t whose initial points form a Poisson point process with intensity \(\lambda >0\). When \(d\ge 4\), the Brownian paths are replaced by Wiener sausages with radius \(r>0\). We establish that, for \(d=1\) and all choices of t, no percolation occurs, whereas for \(d\ge 2\), there is a non-trivial percolation transition in t, provided \(\lambda \) and r are chosen properly. The last statement means that \(\lambda \) has to be chosen to be strictly smaller than the critical percolation parameter for the occupied set at time zero (which is infinite when \(d\in \{2,3\}\), but finite and dependent on r when \(d\ge 4\)). We further show that for all \(d\ge 2\), the unbounded cluster in the supercritical phase is unique. Along the way a finite box criterion for non-percolation in the Boolean model is extended to radius distributions with an exponential tail. This may be of independent interest. The present paper settles the basic properties of the model and should be viewed as a springboard for finer results.     

The Dirichlet problem for Einstein metrics on cohomogeneity one manifolds

Let \(G{/}H\) be a compact homogeneous space, and let \(\hat{g}_0\) and \(\hat{g}_1\) be G-invariant Riemannian metrics on \(G/H\). We consider the problem of finding a G-invariant Einstein metric g on the manifold \(G/H\times [0,1]\) subject to the constraint that g restricted to \(G{/}H\times \{0\}\) and \(G/H\times \{1\}\) coincides with \(\hat{g}_0\) and \(\hat{g}_1\), respectively. By assuming that the isotropy representation of \(G/H\) consists of pairwise inequivalent irreducible summands, we show that we can always find such an Einstein metric.     

Existence of generalized Latin squares which are not embeddable in any group

Let n be a positive integer. A generalized Latin square of order n is an \(n\times n\) matrix such that the elements in each row and each column are distinct. In this paper, we show that for any integer \(n\ge 6\) and any integer m where \(m\in \left\{ n, n+1, \dots , \frac{n(n+1)}{2}-2\right\} \), there exists a commutative generalized Latin square of order n with m distinct elements which is not embeddable in any group. In addition, we show that for any integer \(r\ge 3\) and any integer s where \(s\in \{ r, r+1, \dots , r^2-2\}\), there exists a non-commutative generalized Latin square of order r with s distinct elements which is not embeddable in any group.     

Group divisible designs with large block sizes

For positive integers n, k with \(3\le k\le n\), let \(X=\mathbb {F}_{2^n}\setminus \{0,1\}\), \({\mathcal {G}}=\{\{x,x+1\}:x\in X\}\), and \({\mathcal {B}}_k=\left\{ \{x_1,x_2,\ldots ,x_k\}\!\subset \!X:\sum \limits _{i=1}^kx_i=1,\ \sum \limits _{i\in I}x_i\!\ne \!1\ \mathrm{for\ any}\ \emptyset \!\ne \!I\!\subsetneqq \!\{1,2,\ldots ,k\}\right\} \). Lee et al. used the inclusion–exclusion principle to show that the triple \((X,{\mathcal {G}},{\mathcal {B}}_k)\) is a \((k,\lambda _k)\)-GDD of type \(2^{2^{n-1}-1}\) for \(k\in \{3,4,5,6,7\}\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(2^n-2^i)}{(k-2)!}\) (Lee et al. in Des Codes Cryptogr,  https://doi.org/10.1007/s10623-017-0395-8, 2017). They conjectured that \((X,{\mathcal {G}},{\mathcal {B}}_k)\) is also a \((k,\lambda _k)\)-GDD of type \(2^{2^{n-1}-1}\) for any integer \(k\ge 8\). In this paper, we use a similar construction and counting principles to show that there is a \((k,\lambda _k)\)-GDD of type \((q^2-q)^{(q^{n-1}-1)/(q-1)}\) for any prime power q and any integers k, n with \(3\le k\le n\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(q^n-q^i)}{(k-2)!}\). Consequently, their conjecture holds. Such a method is also generalized to yield a \((k,\lambda _k)\)-GDD of type \((q^{\ell +1}-q^{\ell })^{(q^{n-\ell }-1)/(q-1)}\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(q^n-q^{\ell +i-1})}{(k-2)!}\) and \(k+\ell \le n+1\).     

Few associative triples,isotopisms and groups

Let Q be a quasigroup. For \(\alpha ,\beta \in S_Q\) let \(Q_{\alpha ,\beta }\) be the principal isotope \(x*y = \alpha (x)\beta (y)\). Put \(\mathbf a(Q)= |\{(x,y,z)\in Q^3;\) \(x(yz)) = (xy)z\}|\) and assume that \(|Q|=n\). Then \(\sum _{\alpha ,\beta }\mathbf a(Q_{\alpha ,\beta })/(n!)^2 = n^2(1+(n-1)^{-1})\), and for every \(\alpha \in S_Q\) there is \(\sum _\beta \mathbf a(Q_{\alpha ,\beta })/n! = n(n-1)^{-1}\sum _x(f_x^2-2f_x+n)\ge n^2\), where \(f_x=|\{y\in Q;\) \( y = \alpha (y)x\}|\). If G is a group and \(\alpha \) is an orthomorphism, then \(\mathbf a(G_{\alpha ,\beta })=n^2\) for every \(\beta \in S_Q\). A detailed case study of \(\mathbf a(G_{\alpha ,\beta })\) is made for the situation when \(G = \mathbb Z_{2d}\), and both \(\alpha \) and \(\beta \) are “natural” near-orthomorphisms. Asymptotically, \(\mathbf a(G_{\alpha ,\beta })>3n\) if G is an abelian group of order n. Computational results: \(\mathbf a(7) = 17\) and \(\mathbf a(8) \le 21\), where \(\mathbf a(n) = \min \{\mathbf a(Q);\) \( |Q|=n\}\). There are also determined minimum values for \(\mathbf a(G_{\alpha ,\beta })\), G a group of order \(\le 8\).     

Lengths of words in transformation semigroups generated by digraphs

Given a simple digraph D on n vertices (with \(n\ge 2\)), there is a natural construction of a semigroup of transformations \(\langle D\rangle \). For any edge (a, b) of D, let \(a\rightarrow b\) be the idempotent of rank \(n-1\) mapping a to b and fixing all vertices other than a; then, define \(\langle D\rangle \) to be the semigroup generated by \(a \rightarrow b\) for all \((a,b) \in E(D)\). For \(\alpha \in \langle D\rangle \), let \(\ell (D,\alpha )\) be the minimal length of a word in E(D) expressing \(\alpha \). It is well known that the semigroup \(\mathrm {Sing}_n\) of all transformations of rank at most \(n-1\) is generated by its idempotents of rank \(n-1\). When \(D=K_n\) is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate \(\ell (K_n,\alpha )\), for any \(\alpha \in \langle K_n\rangle = \mathrm {Sing}_n\); however, no analogous non-trivial results are known when \(D \ne K_n\). In this paper, we characterise all simple digraphs D such that either \(\ell (D,\alpha )\) is equal to Howie–Iwahori’s formula for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {fix}(\alpha )\) for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {rk}(\alpha )\) for all \(\alpha \in \langle D\rangle \). We also obtain bounds for \(\ell (D,\alpha )\) when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank \(n-1\) of \(\mathrm {Sing}_n\)). We finish the paper with a list of conjectures and open problems.     

The convolution algebra

For L a complete lattice L and \(\mathfrak {X}=(X,(R_i)_I)\) a relational structure, we introduce the convolution algebra \(L^{\mathfrak {X}}\). This algebra consists of the lattice \(L^X\) equipped with an additional \(n_i\)-ary operation \(f_i\) for each \(n_i+1\)-ary relation \(R_i\) of \(\mathfrak {X}\). For \(\alpha _1,\ldots ,\alpha _{n_i}\in L^X\) and \(x\in X\) we set \(f_i(\alpha _1,\ldots ,\alpha _{n_i})(x)=\bigvee \{\alpha _1(x_1)\wedge \cdots \wedge \alpha _{n_i}(x_{n_i}):(x_1,\ldots ,x_{n_i},x)\in R_i\}\). For the 2-element lattice 2, \(2^\mathfrak {X}\) is the reduct of the familiar complex algebra \(\mathfrak {X}^+\) obtained by removing Boolean complementation from the signature. It is shown that this construction is bifunctorial and behaves well with respect to one-one and onto maps and with respect to products. When L is the reduct of a complete Heyting algebra, the operations of \(L^\mathfrak {X}\) are completely additive in each coordinate and \(L^\mathfrak {X}\) is in the variety generated by \(2^\mathfrak {X}\). Extensions to the construction are made to allow for completely multiplicative operations defined through meets instead of joins, as well as modifications to allow for convolutions of relational structures with partial orderings. Several examples are given.     

Revisiting Fryszkowski’s problem

Professor Andrzej Fryszkowski formulated, at the 2nd Symposium on Nonlinear Analysis in Toruń, September 13–17, 1999, the following problem: given \(\alpha \in (0,1)\), an arbitrary non-empty set \(\Omega \) and a set-valued mapping \(F:\Omega \rightarrow 2^{\Omega }\), find necessary and (or) sufficient conditions for the existence of a (complete) metric d on \(\Omega \) having the property that F is a Nadler set-valued \(\alpha \)-contraction with respect to d. Com?neci (Stud. Univ. Babe?-Bolyai Math. 62:537–542, 2017) provided necessary and sufficient conditions for the existence of a complete and bounded metric d on \(\Omega \) having the property that F is a Nadler set-valued \(\alpha \)-contraction with respect to d, in case that \(\alpha \in (0,\frac{1}{2})\) and there exists \(z\in \Omega \) such that \(F(z)=\{z\}\) . We improve Com?neci’s result by allowing \(\alpha \) to belong to the interval (0, 1). In addition, we provide necessary and sufficient conditions for the existence of a complete and bounded metric d on \(\Omega \) such that F is a Nadler set-valued \(\alpha \)-similarity with respect to d, in case that \(\alpha \in (0,1)\), there exists \(z\in \Omega \) such that \(F(z)=\{z\}\) and F is non-overlapping.     

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

On the cardinality of positively linearly independent sets

Positive bases, which play a key role in understanding derivative free optimization methods that use a direct search framework, are positive spanning sets that are positively linearly independent. The cardinality of a positive basis in \(\mathbb {R}^n\) has been established to be between \(n+1\) and 2n (with both extremes existing). The lower bound is immediate from being a positive spanning set, while the upper bound uses both positive spanning and positively linearly independent. In this note, we provide details proving that a positively linearly independent set in \(\mathbb {R}^n\) for \(n \in \{1, 2\}\) has at most 2n elements, but a positively linearly independent set in \(\mathbb {R}^n\) for \(n\ge 3\) can have an arbitrary number of elements.     

Monochromatic Solutions for Multi-Term Unknowns

Given integers \(k\ge 2\), \(n \ge 2\), \(m \ge 2\) and \( a_1,a_2,\ldots ,a_m \in {\mathbb {Z}}{\backslash }{\{0\}}\), and let \(f(z)= \sum _{j=0}^{n}c_jz^j\) be a polynomial of integer coefficients with \(c_n>0\) and \((\sum _{i=1}^ma_i)|f(z)\) for some integer z. For a k-coloring of \([N]=\{1,2,\ldots ,N\}\), we say that there is a monochromatic solution of the equation \(a_1x_1+a_2x_2+\cdots +a_mx_m=f(z)\) if there exist pairwise distinct \(x_1,x_2,\ldots ,x_m\in [N]\) all of the same color such that the equation holds for some \(z\in \mathbb {Z}\). Problems of this type are often referred to as Ramsey-type problems. In this paper, it is shown that if \(a_i>0\) for \(1\le i\le m\), then there exists an integer \(N_0=N(k,m,n)\) such that for \(N\ge N_0\), each k-coloring of [N] contains a monochromatic solution \(x_1,x_2,\ldots ,x_m\) of the equation \(a_1x_1+a_2x_2+ \cdots +a_mx_m= f(z)\). Moreover, if n is odd and there are \(a_i\) and \(a_j\) such that \(a_ia_j<0\) for some \(1 \le i\ne j\le m\), then the assertion holds similarly.     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

On Expanding Neighborhoods of Local Universality of Gaussian Unitary Ensembles

The classical universality theorem states that the Christoffel–Darboux kernel of the Hermite polynomials scaled by a factor of \(1/\sqrt n\) tends to the sine kernel in local variables \(\tilde x,\tilde y\) in a neighborhood of a point \(x^*\in(-\sqrt 2,\sqrt 2)\)). This classical result is well known for \(\tilde x,\tilde y\in{K}\Subset\mathbb{R}\). In this paper, we show that this classical result remains valid for expanding compact sets K = K(n). An interesting phenomenon of admissible dependence of the expansion rate of compact sets K(n) on x* is established. For \(x^*\in(-\sqrt 2,\sqrt 2)\backslash\left\{0\right\}\)) and for x* = 0, there are different growth regimes of compact sets K(n). A transient regime is found.     

Density of translates in weighted $${{\varvec{L}}}^{{\varvec{p}}}$$ spaces on locally compact groups

Let G be a locally compact group, and let \(1\leqslant p < \infty \). Consider the weighted \(L^p\)-space \(L^p(G,\omega )=\{f:\int |f\omega |^p<\infty \}\), where \(\omega :G\rightarrow \mathbb {R}\) is a positive measurable function. Under appropriate conditions on \(\omega \), G acts on \(L^p(G,\omega )\) by translations. When is this action hypercyclic, that is, there is a function in this space such that the set of all its translations is dense in \(L^p(G,\omega )\)? Salas (Trans Am Math Soc 347:993–1004, 1995) gave a criterion of hypercyclicity in the case \(G=\mathbb {Z}\). Under mild assumptions, we present a corresponding characterization for a general locally compact group G. Our results are obtained in a more general setting when the translations only by a subset \(S\subset G\) are considered.     

Algorithms for positive semidefinite factorization

This paper considers the problem of positive semidefinite factorization (PSD factorization), a generalization of exact nonnegative matrix factorization. Given an m-by-n nonnegative matrix X and an integer k, the PSD factorization problem consists in finding, if possible, symmetric k-by-k positive semidefinite matrices \(\{A^1,\ldots ,A^m\}\) and \(\{B^1,\ldots ,B^n\}\) such that \(X_{i,j}=\text {trace}(A^iB^j)\) for \(i=1,\ldots ,m\), and \(j=1,\ldots ,n\). PSD factorization is NP-hard. In this work, we introduce several local optimization schemes to tackle this problem: a fast projected gradient method and two algorithms based on the coordinate descent framework. The main application of PSD factorization is the computation of semidefinite extensions, that is, the representations of polyhedrons as projections of spectrahedra, for which the matrix to be factorized is the slack matrix of the polyhedron. We compare the performance of our algorithms on this class of problems. In particular, we compute the PSD extensions of size \(k=1+ \lceil \log _2(n) \rceil \) for the regular n-gons when \(n=5\), 8 and 10. We also show how to generalize our algorithms to compute the square root rank (which is the size of the factors in a PSD factorization where all factor matrices \(A^i\) and \(B^j\) have rank one) and completely PSD factorizations (which is the special case where the input matrix is symmetric and equality \(A^i=B^i\) is required for all i).     

Some results on generalized strong external difference families

A generalized strong external difference family (briefly \((v, m; k_1,\dots ,k_m; \lambda _1,\dots ,\lambda _m)\)-GSEDF) was introduced by Paterson and Stinson in 2016. In this paper, we give some nonexistence results for GSEDFs. In particular, we prove that a \((v, 3;k_1,k_2,k_3; \lambda _1,\lambda _2,\lambda _3)\)-GSEDF does not exist when \(k_1+k_2+k_3< v\). We also give a first recursive construction for GSEDFs and prove that if there is a \((v,2;2\lambda ,\frac{v-1}{2};\lambda ,\lambda )\)-GSEDF, then there is a \((vt,2;4\lambda ,\frac{vt-1}{2};2\lambda ,2\lambda )\)-GSEDF with \(v>1\), \(t>1\) and \(v\equiv t\equiv 1\pmod 2\). Then we use it to obtain some new GSEDFs for \(m=2\). In particular, for any prime power q with \(q\equiv 1\pmod 4\), we show that there exists a \((qt, 2;(q-1)2^{n-1},\frac{qt-1}{2};(q-1)2^{n-2},(q-1)2^{n-2})\)-GSEDF, where \(t=p_1p_2\dots p_n\), \(p_i>1\), \(1\le i\le n\), \(p_1, p_2,\dots ,p_n\) are odd integers.