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.     

The order continuity in ordered algebras

Let A be an ordered algebra with a unit \(\mathbf{e}\) and a cone \(A^+\). The class of order continuous elements \(A_\mathrm{n}\) of A is introduced and studied. If \(A=L(E)\), where E is a Dedekind complete Riesz space, this class coincides with the band \(L_\mathrm{n}(E)\) of all order continuous operators on E. Special subclasses of \(A_\mathrm {n}\) are considered. Firstly, the order ideal \(A_\mathbf{e}\) generated by \(\mathbf{e}\). It is shown that \(A_\mathbf{e}\) can be embedded into the algebra of continuous functions and, in particular, is a commutative subalgebra of A. If A is an ordered Banach algebra with normal cone \(A^+\) then \(A_\mathbf{e}\) is an AM-space and is closed in A. Secondly, the notion of an orthomorphism in the ordered algebra A is introduced. Among others, the conditions under which orthomorphisms are order continuous, are considered. In the second part, the main emphasis will be on the case of an ordered \(C^*\)-algebra A and, in particular, on the case of the algebra B(H), where H is an ordered Hilbert space with self-adjoint cone \(H^+\). If the cone \(A^+\) is normal then every element of \(A_\mathbf{e}\) is hermitian. In H the operations are introduced which coincide with the lattice ones when H is a Riesz space. It is shown that every regular \(T\in B(H)\) is an order continuous element and operators \(T\in (B(H))_I\) have properties which are analogous to the properties of orthomorphisms on Riesz spaces.     

Nonlinear Maps Preserving the Jordan Triple *-Product on Factor von Neumann Algebras

Let A and B be two factor von Neumann algebras. For A, B ∈ A, define by [A, B]_*= AB-BA~*the skew Lie product of A and B. In this article, it is proved that a bijective map Φ : A → B satisfies Φ([[A, B]_*, C]_*) = [[Φ(A), Φ(B)]_*, Φ(C)]_*for all A, B, C ∈ A if and only if Φ is a linear *-isomorphism, or a conjugate linear *-isomorphism, or the negative of a linear *-isomorphism, or the negative of a conjugate linear *-isomorphism.     

Conflict free colorings of nonuniform systems of infinite sets

If \(\mathcal{H}\) is a system of infinite sets, |A∩B|<r for \({A\ne B\in\mathcal{H}}\) (r<ω) then \(\mathcal{H}\) has a conflict free coloring with ω colors, i.e., a function \(F\colon {\bigcup\mathcal{H}\to\omega}\) so that each \(A\in\mathcal{H}\) has a color i<ω with |F ^?1(i)∩A|=1.     

Inflation of Finite Lattices Along All-or-nothing Sets

We introduce a new generalization of Alan Day’s doubling construction. For ordered sets \(\mathcal {L}\) and \(\mathcal {K}\) and a subset \(E \subseteq \ \leq _{\mathcal {L}}\) we define the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) arising from inflation of \(\mathcal {L}\) along E by \(\mathcal {K}\). Under the restriction that \(\mathcal {L}\) and \(\mathcal {K}\) are finite lattices, we find those subsets \(E \subseteq \ \leq _{\mathcal {L}}\) such that the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) is a lattice. Finite lattices that can be constructed in this way are classified in terms of their congruence lattices.A finite lattice is binary cut-through codable if and only if there exists a 0?1 spanning chain \(\left \{\theta _{i}\colon 0 \leq i \leq n \right \}\) in \(Con(\mathcal {L})\) such that the cardinality of the largest block of ?? _i /?? _i?1 is 2 for every i with 1≤i≤n. These are exactly the lattices that can be constructed by inflation from the 1-element lattice using only the 2-element lattice. We investigate the structure of binary cut-through codable lattices and describe an infinite class of lattices that generate binary cut-through codable varieties.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

On ℤ<Subscript>2</Subscript>-graded identities of the super tensor product of <Emphasis Type="Italic">UT</Emphasis><Subscript>2</Subscript>(<Emphasis Type="Italic">F</Emphasis>) by the Grassmann algebra

Let F be a field of characteristic zero and E be the unitary Grassmann algebra generated over an infinite-dimensional F-vector space L. Denote by \(\mathcal{E} = \mathcal{E}^{(0)} \oplus \mathcal{E}^{(1)}\) an arbitrary ?₂-grading of E such that the subspace L is homogeneous. Given a superalgebra A = A ⁽⁰⁾ ⊕ A ⁽¹⁾, define the superalgebra \(A\hat \otimes \mathcal{E}\) by \(A\hat \otimes \mathcal{E} = (A^{(0)} \otimes \mathcal{E}^{(0)} ) \oplus (A^{(1)} \otimes \mathcal{E}^{(1)} )\). Note that when E is the canonical grading of E then \(A\hat \otimes \mathcal{E}\) is the Grassmann envelope of A. In this work we find bases of ?₂-graded identities and we describe the ?₂-graded codimension and cocharacter sequences for the superalgebras \(UT_2 (F)\hat \otimes \mathcal{E}\), when the algebra UT ₂(F) of 2 ×2 upper triangular matrices over F is endowed with its canonical grading.     

Recurrent Dirichlet Forms and Markov Property of Associated Gaussian Fields

For the extended Dirichlet space \(\mathcal {F}_{e}\) of a general irreducible recurrent regular Dirichlet form \((\mathcal {E},\mathcal {F})\) on L ²(E;m), we consider the family \(\mathbb {G}(\mathcal {E})=\{X_{u};u\in \mathcal {F}_{e}\}\) of centered Gaussian random variables defined on a probability space \(({\Omega }, \mathcal {B}, \mathbb {P})\) indexed by the elements of \(\mathcal {F}_{e}\) and possessing the Dirichlet form \(\mathcal {E}\) as its covariance. We formulate the Markov property of the Gaussian field \(\mathbb {G}(\mathcal {E})\) by associating with each set A ? E the sub-σ-field σ(A) of \(\mathcal {B}\) generated by X _u for every \(u\in \mathcal {F}_{e}\) whose spectrum s(u) is contained in A. Under a mild absolute continuity condition on the transition function of the Hunt process associated with \((\mathcal {E}, \mathcal {F})\), we prove the equivalence of the Markov property of \(\mathbb {G}(\mathcal {E})\) and the local property of \((\mathcal {E},\mathcal {F})\). One of the key ingredients in the proof is in that we construct potentials of finite signed measures of zero total mass and show that, for any Borel set B with m(B) >?0, any function \(u\in \mathcal {F}_{e}\) with s(u) ? B can be approximated by a sequence of potentials of measures supported by B.     

Extremes of Gaussian random fields with regularly varying dependence structure

Let \(X(t), t\in \mathcal {T}\) be a centered Gaussian random field with variance function σ ²(?) that attains its maximum at the unique point \(t_{0}\in \mathcal {T}\), and let \(M(\mathcal {T})=\sup _{t\in \mathcal {T}} X(t)\). For \(\mathcal {T}\) a compact subset of ?, the current literature explains the asymptotic tail behaviour of \(M(\mathcal {T})\) under some regularity conditions including that 1 ? σ(t) has a polynomial decrease to 0 as t → t ₀. In this contribution we consider more general case that 1 ? σ(t) is regularly varying at t ₀. We extend our analysis to Gaussian random fields defined on some compact set \(\mathcal {T}\subset \mathbb {R}^{2}\), deriving the exact tail asymptotics of \(M(\mathcal {T})\) for the class of Gaussian random fields with variance and correlation functions being regularly varying at t ₀. A crucial novel element is the analysis of families of Gaussian random fields that do not possess locally additive dependence structures, which leads to qualitatively new types of asymptotics.     

Symmetric Pairs and Self-Adjoint Extensions of Operators,with Applications to Energy Networks

We provide a streamlined construction of the Friedrichs extension of a densely-defined self-adjoint and semibounded operator A on a Hilbert space \(\mathcal {H}\), by means of a symmetric pair of operators. A symmetric pair is comprised of densely defined operators \(J: \mathcal {H}_1 \rightarrow \mathcal {H}_2\) and \(K: \mathcal {H}_2 \rightarrow \mathcal {H}_1\) which are compatible in a certain sense. With the appropriate definitions of \(\mathcal {H}_1\) and J in terms of A and \(\mathcal {H}\), we show that \((\textit{JJ}^\star )^{-1}\) is the Friedrichs extension of A. Furthermore, we use related ideas (including the notion of unbounded containment) to construct a generalization of the construction of the Krein extension of A as laid out in a previous paper of the authors. These results are applied to the study of the graph Laplacian on infinite networks, in relation to the Hilbert spaces \(\ell ^2(G)\) and \(\mathcal {H}_{\mathcal {E}}\) (the energy space).     

Generalized Drazin invertibility and local spectral theory

If \(A\in B(\mathcal{X})\) is an upper triangular Banach space operator with diagonal \((A_1,A_2)\), \(A_1\) invertible and \(A_2\) quasinilpotent, then \(A_1^{-1}\oplus A_2\) satisfies either of the single-valued extension property, Dunford’s condition (C), Bishop’s property \((\beta )\), decomposition property \((\delta )\) or is decomposable if and only if \(A_1\) has the property. The operator \(A^{-1}_1\oplus 0\) is subscalar (resp., left polaroid, right polaroid) if and only if \(A_1\) is subscalar (resp., left polaroid, right polaroid). For Drazin invertible operators A, with Drazin inverse B, this implies that B satisfies any one of these properties if and only if A satisfies the property.     

Fractional Differentiability for Solutions of Nonlinear Elliptic Equations

We study nonlinear elliptic equations in divergence form

$$\text {div }{\mathcal A}(x,Du)=\text {div } G.$$

When \({\mathcal A}\) has linear growth in D u, and assuming that \(x\mapsto {\mathcal A}(x,\xi )\) enjoys \(B^{\alpha }_{\frac {n}\alpha , q}\) smoothness, local well-posedness is found in \(B^{\alpha }_{p,q}\) for certain values of \(p\in [2,\frac {n}{\alpha })\) and \(q\in [1,\infty ]\). In the particular case \({\mathcal A}(x,\xi )=A(x)\xi \), G = 0 and \(A\in B^{\alpha }_{\frac {n}\alpha ,q}\), \(1\leq q\leq \infty \), we obtain \(Du\in B^{\alpha }_{p,q}\) for each \(p<\frac {n}\alpha \). Our main tool in the proof is a more general result, that holds also if \({\mathcal A}\) has growth s?1 in D u, 2 ≤ s ≤ n, and asserts local well-posedness in L ^q for each q > s, provided that \(x\mapsto {\mathcal A}(x,\xi )\) satisfies a locally uniform VMO condition.

     

On the peripheral spectrum of positive elements

Let A be an ordered Banach algebra with a unit \(\mathbf{e}\) and a cone \(A^+\). An element p of A is said to be an order idempotent if \(p^2 = p\) and \(0 \le p\le \mathbf{e}\). An element \(a\in A^+\) is said to be irreducible if the relation \((\mathbf{e}-p)ap = 0\), where p is an order idempotent, implies \(p = 0\) or \(p = \mathbf{e}\). For an arbitrary element a of A the peripheral spectrum \(\sigma _\mathrm{per}(a)\) of a is the set \(\sigma _\mathrm{per}(a) = \{\lambda \in \sigma (a):|\lambda | = r(a)\}\), where \(\sigma (a)\) is the spectrum of a and r(a) is the spectral radius of a. We investigate properties of the peripheral spectrum of an irreducible element a. Conditions under which \(\sigma _\mathrm{per}(a)\) contains or coincides with \(r(a)H_m\), where \(H_m\) is the group of all \(m^\mathrm{th}\) roots of unity, and the spectrum \(\sigma (a)\) is invariant under rotation by the angle \(\frac{2\pi }{m}\) for some \(m\in {\mathbb N}\), are given. The correlation between these results and the existence of a cyclic form of a is considered. The conditions under which a is primitive, i.e., \(\sigma _\mathrm{per}(a) = \{r(a)\}\), are studied. The necessary assumptions on the algebra A which imply the validity of these results, are discussed. In particular, the Lotz–Schaefer axiom is introduced and finite-rank elements of A are defined. Other approaches to the notions of irreducibility and primitivity are discussed. Conditions under which the inequalities \(0 \le b < a\) imply \(r(b) < r(a)\) are studied. The closedness of the center \(A_\mathbf{e}\), i.e., of the order ideal generated by \(\mathbf{e}\) in A, is proved.     

A Generalization of Stenger’s Lemma to Maximal Dissipative Operators

It is shown that for any maximal dissipative operator A in some Hilbert space \({\mathcal H}\) , which is the orthogonal sum \({\mathcal H=\mathcal F\oplus \mathcal G}\) of two Hilbert spaces \({\mathcal F,\, \mathcal G}\) with \({{\rm dim}\,\mathcal G < \infty}\) , the compression \({\left. T:=P_\mathcal F\,A\right|_{{\rm dom}\,A\cap\mathcal F}}\) of A to \({\mathcal F}\) is again a maximal dissipative operator in \({\mathcal F}\) .     

Largest initial segments pointwise fixed by automorphisms of models of set theory

Given a model \(\mathcal {M}\) of set theory, and a nontrivial automorphism j of \(\mathcal {M}\), let \(\mathcal {I}_{\mathrm {fix}}(j)\) be the submodel of \(\mathcal {M}\) whose universe consists of elements m of \(\mathcal {M}\) such that \(j(x)=x\) for every x in the transitive closure of m (where the transitive closure of m is computed within \(\mathcal {M}\)). Here we study the class \(\mathcal {C}\) of structures of the form \(\mathcal {I}_{\mathrm {fix}}(j)\), where the ambient model \(\mathcal {M}\) satisfies a frugal yet robust fragment of \(\mathrm {ZFC}\) known as \(\mathrm {MOST}\), and \(j(m)=m\) whenever m is a finite ordinal in the sense of \(\mathcal {M}.\) Our main achievement is the calculation of the theory of \(\mathcal {C}\) as precisely \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm {Collection}\). The following theorems encapsulate our principal results: Theorem A. Every structure in \(\mathcal {C}\) satisfies \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm { Collection}\). Theorem B. Each of the following three conditions is sufficient for a countable structure \(\mathcal {N}\) to be in \(\mathcal {C}\):(a) \(\mathcal {N}\) is a transitive model of \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm {Collection}\).(b) \(\mathcal {N}\) is a recursively saturated model of \(\mathrm {MOST+\Delta }_{0}^{\mathcal {P}}\)-\(\mathrm {Collection}\).(c) \(\mathcal {N}\) is a model of \(\mathrm {ZFC}\). Theorem C. Suppose \(\mathcal {M}\) is a countable recursively saturated model of \(\mathrm {ZFC}\) and I is a proper initial segment of \(\mathrm {Ord}^{\mathcal {M}}\) that is closed under exponentiation and contains \(\omega ^\mathcal {M}\) . There is a group embedding \(j\longmapsto \check{j}\) from \(\mathrm {Aut}(\mathbb {Q})\) into \(\mathrm {Aut}(\mathcal {M})\) such that I is the longest initial segment of \(\mathrm {Ord}^{\mathcal {M}}\) that is pointwise fixed by \(\check{j}\) for every nontrivial \(j\in \mathrm {Aut}(\mathbb {Q}).\) In Theorem C, \(\mathrm {Aut}(X)\) is the group of automorphisms of the structure X, and \(\mathbb {Q}\) is the ordered set of rationals.     

On Riesz Transforms Characterization of <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript> Spaces Associated with Some Schrödinger Operators

Let \(\mathcal Lf(x)=-\Delta f (x)+V(x)f(x)\), V?≥?0, \(V\in L^1_{loc}(\mathbb R^d)\), be a non-negative self-adjoint Schrödinger operator on \(\mathbb R^d\). We say that an L ¹-function f is an element of the Hardy space \(H^1_{\mathcal L}\) if the maximal function

$ \mathcal M_{\mathcal L} f(x)=\sup\limits_{t>0}|e^{-t\mathcal L} f(x)| $

belongs to \(L^1(\mathbb R^d)\). We prove that under certain assumptions on V the space \(H^1_{\mathcal L}\) is also characterized by the Riesz transforms \(R_j=\frac{\partial}{\partial x_j}\mathcal L^{-1\slash 2}\), j?=?1,...,d, associated with \(\mathcal L\). As an example of such a potential V one can take any V?≥?0, \(V\in L^1_{loc}\), in one dimension.

     

Resilience of ranks of higher inclusion matrices

Let \(n \ge r \ge s \ge 0\) be integers and \(\mathcal {F}\) a family of r-subsets of [n]. Let \(W_{r,s}^{\mathcal {F}}\) be the higher inclusion matrix of the subsets in \({{\mathcal {F}}}\) vs. the s-subsets of [n]. When \(\mathcal {F}\) consists of all r-subsets of [n], we shall simply write \(W_{r,s}\) in place of \(W_{r,s}^{\mathcal {F}}\). In this paper we prove that the rank of the higher inclusion matrix \(W_{r,s}\) over an arbitrary field K is resilient. That is, if the size of \(\mathcal {F}\) is “close” to \({n \atopwithdelims ()r}\) then \({{\mathrm{rank}}}_{K}( W_{r,s}^{\mathcal {F}}) = {{\mathrm{rank}}}_{K}(W_{r,s})\), where K is an arbitrary field. Furthermore, we prove that the rank (over a field K) of the higher inclusion matrix of r-subspaces vs. s-subspaces of an n-dimensional vector space over \({\mathbb {F}}_q\) is also resilient if \(\mathrm{char}(K)\) is coprime to q.     

Spectral multiplier theorems and averaged <Emphasis Type="Italic">R</Emphasis>-boundedness

Let A be a 0-sectorial operator with a bounded \(H^\infty (\Sigma _\sigma )\)-calculus for some \(\sigma \in (0,\pi ),\) e.g. a Laplace type operator on \(L^p(\Omega ),\, 1< p < \infty ,\) where \(\Omega \) is a manifold or a graph. We show that A has a \(\mathcal {H}^\alpha _2(\mathbb {R}_+)\) Hörmander functional calculus if and only if certain operator families derived from the resolvent \((\lambda - A)^{-1},\) the semigroup \(e^{-zA},\) the wave operators \(e^{itA}\) or the imaginary powers \(A^{it}\) of A are R-bounded in an \(L^2\)-averaged sense. If X is an \(L^p(\Omega )\) space with \(1 \le p < \infty \), R-boundedness reduces to well-known estimates of square sums.     

Eichler’s commutation relation and some other invariant subspaces of Hecke operators

Let k be an odd positive integer, L a lattice on a regular positive definite k-dimensional quadratic space over \(\mathbb {Q}\), \(N_L\) the level of L, and \(\mathscr {M}(L)\)  be the linear space of \(\theta \)-series attached to the distinct classes in the genus of L. We prove that, for an odd prime \(p|N_L\), if \(L_p=L_{p,1}\,\bot \, L_{p,2}\), where \(L_{p,1}\) is unimodular, \(L_{p,2}\) is (p)-modular, and \(\mathbb {Q}_pL_{p,2}\) is anisotropic, then \(\mathscr {M}(L;p):=\) \(\mathscr {M}(L)\) \(+T_{p^2}.\) \(\mathscr {M}(L)\)  is stable under the Hecke operator \(T_{p^2}\). If \(L_2\) is isometric to \(\left( \begin{array}{ll}0&{}\frac{1}{2}\\ \frac{1}{2}&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle \varepsilon \rangle \) or \(\left( \begin{array}{ll}0&{}\frac{1}{2}\\ \frac{1}{2}&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle 2\varepsilon \rangle \) or \(\left( \begin{array}{ll}0&{}1\\ 1&{}0\end{array}\right) ^{\kappa }\,\bot \, \langle \varepsilon \rangle \) with \(\varepsilon \in \mathbb {Z}_2^{\times }\) and \(\kappa :=\frac{k-1}{2}\), then \(\mathscr {M}(L;2):=T_{2^2}.\mathscr {M}(L)+T_{2^2}^2.\,\mathscr {M}(L)\) is stable under the Hecke operator \(T_{2^2}\). Furthermore, we determine some invariant subspaces of the cusp forms for the Hecke operators.     

Isometric multipliers of a vector valued Beurling algebra on a discrete semigroup

Let (S,ω) be a weighted abelian semigroup, let M _ω (S) be the semigroup of ω-bounded multipliers of S, and let \(\mathcal {A}\) be a strictly convex commutative Banach algebra with identity. It is shown that T is an onto isometric multiplier of \(\ell ^{1}(S,\omega , \mathcal {A})\) if and only if there exists an invertible σ ∈ M _ω (S), a unitary point \(a \in \mathcal {A}\), and a k>0 such that \(T(f)= ka{\sum }_{x \in S} f(x)\delta _{\sigma (x)}\) for each \(f={\sum }_{x \in S}f(x)\delta _{x} \in \ell ^{1}(S,\omega ,\mathcal {A})\). It is also shown that an isomorphism from \(\ell ^{1}(S_{1},\omega _{1},\mathcal {A})\) onto \(\ell ^{1}(S_{2},\omega _{2}, \mathcal {B})\) induces an isomorphism from \(M(\ell ^{1}(S_{1},\omega _{1},\mathcal {A}))\), the set of all multipliers of \(\ell ^{1}(S_{1},\omega _{1},\mathcal {A})\), onto \(M(\ell ^{1}(S_{2},\omega _{2},\mathcal {B}))\).