Complexity and structure of near-minimal contact circuits for elementary symmetric functions

The paper studies the problem of the synthesis of contact circuits for elementary symmetric functions. The structure of minimal contact circuits realizing elementary symmetric functions is established and the estimates of the complexity of the obtained circuits, which are accurate to within an additive constant, are determined. It is proved that, for substantially large n, the complexity of an elementary symmetric function of n variables with the working number w satisfies the relation L(s _n ^w ) = (2w + 1)n ? B _w , whereB _w is a nonnegative constant.     

Improved Sufficient Conditions for the Existence of Anti-Directed Hamiltonian Cycles in Digraphs

Let D be a directed graph of order n. An anti-directed (hamiltonian) cycle H in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. In this paper we give sufficient conditions for the existence of anti-directed hamiltonian cycles. Specifically, we prove that a directed graph D of even order n with minimum indegree and outdegree greater than ${\frac{1}{2}n + 7\sqrt{n}/3}$ contains an anti-directed hamiltonian cycle. In addition, we show that D contains anti-directed cycles of all possible (even) lengths when n is sufficiently large and has minimum in- and out-degree at least ${(1/2+ \epsilon)n}$ for any ${\epsilon > 0}$ .     

The extreme bodies in the set of plane convex bodies with a given width function

Let \(\bar K\) (w) denote the class of plane convex bodies having a width functionw. Examining the length measure of the boundary of a convex body in \(\bar K\) (w), a characterization is given for the extreme (indecomposable) bodies in \(\bar K\) (w). This is a generalization of the solution previously given by the author in Israel J. Math. (1974) for the case wherew′ is absolutely continuous.     

Moments of Two-Variable Functions and the Uniqueness of Graph Limits

For a symmetric bounded measurable function W on [0, 1]² and a simple graph F, the homomorphism density $t(F,W) = \int _{[0,1]^{V (F)}} \prod_ {i j\in E(F)} W(x_i, x_j)dx .$ can be thought of as a “moment” of W. We prove that every such function is determined by its moments up to a measure preserving transformation of the variables. The main motivation for this result comes from the theory of convergent graph sequences. A sequence (G _n ) of dense graphs is said to be convergent if the probability, t(F, G _n ), that a random map from V(F) into V(G _n ) is a homomorphism converges for every simple graph F. The limiting density can be expressed as t(F, W) for a symmetric bounded measurable function W on [0, 1]². Our results imply in particular that the limit of a convergent graph sequence is unique up to measure preserving transformation.     

The de Jongh property for Basic Arithmetic

We prove that Basic Arithmetic, BA, has the de Jongh property, i.e., for any propositional formula A(p ₁,..., p _n ) built up of atoms p ₁,..., p _n , BPC \({\vdash}\) A(p ₁,..., p _n ) if and only if for all arithmetical sentences B ₁,..., B _n , BA \({\vdash}\) A(B ₁,..., B _n ). The technique used in our proof can easily be applied to some known extensions of BA.     

Determining Sets, Resolving Sets, and the Exchange Property

A subset U of vertices of a graph G is called a determining set if every automorphism of G is uniquely determined by its action on the vertices of U. A subset W is called a resolving set if every vertex in G is uniquely determined by its distances to the vertices of W. Determining (resolving) sets are said to have the exchange property in G if whenever S and R are minimal determining (resolving) sets for G and ${r\in R}$ , then there exists ${s\in S}$ so that ${S-\{s\} \cup \{r\}}$ is a minimal determining (resolving) set. This work examines graph families in which these sets do, or do not, have the exchange property. This paper shows that neither determining sets nor resolving sets have the exchange property in all graphs, but that both have the exchange property in trees. It also gives an infinite graph family (n-wheels where n ≥ 8) in which determining sets have the exchange property but resolving sets do not. Further, this paper provides necessary and sufficient conditions for determining sets to have the exchange property in an outerplanar graph.     

Reeb Graphs: Approximation and Persistence

Given a continuous function f:X→? on a topological space X, its level set f ^?1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph, which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H ₁-homology of the Reeb graph from P. It takes O(nlogn) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm for computing the rank of H ₁(M) from point data. The best-known previous algorithm for this problem takes O(n ³) time for point data. The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H ₁-homology for the Reeb graphs in $O(n n_{e}^{3})$ time, where n is the size of the 2-skeleton and n _e is the number of edges in K.     

Unitary Equivalence of Proper Extensions of a Symmetric Operator and the Weyl Function

Let A be a densely defined simple symmetric operator in ${\mathfrak{H}}$ , let ${\Pi=\{\mathcal{H},\Gamma_0, \Gamma_1}\}$ be a boundary triplet for A ^* and let M(·) be the corresponding Weyl function. It is known that the Weyl function M(·) determines the boundary triplet Π, in particular, the pair {A, A ₀}, uniquely up to the unitary similarity. Here ${A_0 := A^* \upharpoonright \text{ker}\, \Gamma_0 ( = A^*_0)}$ . At the same time the Weyl function corresponding to a boundary triplet for a dual pair of operators defines it uniquely only up to the weak similarity. We consider a symmetric dual pair {A, A} with symmetric ${A \subset A^*}$ and a special boundary triplet ${\widetilde{\Pi}}$ for{A, A} such that the corresponding Weyl function is ${\widetilde{M}(z) = K^*(B-M(z))^{-1} K}$ , where B is a non-self-adjoint bounded operator in ${\mathcal{H}}$ . We are interested in the problem whether the result on the unitary similarity remains valid for ${\widetilde{M}(\cdot)}$ in place of M(·). We indicate some sufficient conditions in terms of the operators A ₀ and ${A_B= A^* \upharpoonright \text{ker}\, (\Gamma_1-B \Gamma_0)}$ , which guaranty an affirmative answer to this problem. Applying the abstract results to the minimal symmetric 2nth order ordinary differential operator A in ${L^2(\mathbb{R}_+)}$ , we show that ${\widetilde{M}(\cdot)}$ defined in ${\Omega_+ \subset \mathbb{C}_+}$ determines the Dirichlet and Neumann realizations uniquely up to the unitary equivalence. At the same time similar result for realizations of Dirac operator fails. We obtain also some negative abstract results demonstrating that in general the Weyl function ${\widetilde{M}(\cdot)}$ does not determine A _B even up to the similarity.     

Numerical Radii for Tensor Products of Operators

For bounded linear operators A and B on Hilbert spaces H and K, respectively, it is known that the numerical radii of A, B and ${A\otimes B}$ are related by the inequalities ${w(A)w(B)\le w(A\otimes B)\le {\rm min}\{\|A\|w(B), w(A)\|B\|\}}$ . In this paper, we show that (1) if ${w(A\otimes B) = w(A)w(B)}$ , then w(A) = ρ(A) or w(B) = ρ(B), where ρ(·) denotes the spectral radius of an operator, and (2) if A is hyponormal, then ${w(A\otimes B) = w(A)w(B) = \|A\|w(B)}$ . Here (2) confirms a conjecture of Shiu’s and is proven via dilating the hyponormal A to a normal operator N with the spectrum of N contained in that of A. The latter is obtained from the Sz.-Nagy–Foia? dilation theory.     

Treewidth computation and extremal combinatorics

For a given graph G and integers b,f ≥0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by removing f vertices. We prove that every graph on n vertices contains at most $n\left( {_b^{b + f} } \right)$ such vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a given n-vertex graph G

1. compute the treewidth of G in time O(1.7549 ⁿ ) by making use of exponential space and in time O(2.6151 ⁿ ) and polynomial space
2. decide in time O(n ⁵· $_{k + 2}^{\left\lceil {(2n + k + 8)/3} \right\rceil } $ ) if the treewidth of G is at most k
3. list all minimal separators of G in time O(1.6181 ⁿ ) and all potential maximal cliques of G in time O(1.7549 ⁿ ).

This significantly improves previous algorithms for these problems.     

Metrization of Weighted Graphs

We find a set of necessary and sufficient conditions under which the weight ${w: E \rightarrow \mathbb{R}^{+}}$ on the graph G = (V, E) can be extended to a pseudometric ${d : V \times V \rightarrow \mathbb{R}^{+}}$ . We describe the structure of graphs G for which the set ${\mathfrak{M}_{w}}$ of all such extensions contains a metric whenever w is strictly positive. Ordering ${\mathfrak{M}_{w}}$ by the pointwise order, we have found that the posets $({\mathfrak{M}_{w}, \leqslant)}$ contain the least elements ρ _0,w if and only if G is a complete k-partite graph with ${k \, \geqslant \, 2}$ . In this case the symmetric functions ${f : V \times V \rightarrow \mathbb{R}^{+}}$ , lying between ρ _0,w and the shortest-path pseudometric, belong to ${\mathfrak{M}_{w}}$ for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.     

On the Connectivity of Visibility Graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71?C93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)??deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most ? collinear vertices has connectivity at least $\frac{n-1}{\ell-1}$ , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that ?=4 we improve this bound to two thirds of the minimum degree.     

Dimension Reduction by Random Hyperplane Tessellations

Given a subset K of the unit Euclidean sphere, we estimate the minimal number m=m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x,y∈K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m=O(w(K)²) where w(K) is the Gaussian mean width of K. Using the map that sends x∈K to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of $\mathbb{R}^{n}$ embeds into the Hamming cube {?1,1} ^m with a small distortion in the Gromov–Haussdorff metric. Since for many sets K one has m=m(K)?n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces.     

Commutators of the fractional maximal function on variable exponent Lebesgue spaces

Let \({M_\beta }\) be the fractional maximal function. The commutator generated by \({M_\beta }\) and a suitable function b is defined by \([{M_\beta },b]f = {M_\beta }(bf) - b{M_\beta }(f)\) . Denote by P(? ⁿ ) the set of all measurable functions p(·): ? ⁿ → [1,∞) such that $1 < p_ - : = \mathop {es\sin fp(x)}\limits_{x \in \mathbb{R}^n } andp_ + : = \mathop {es\operatorname{s} \sup p(x) < \infty }\limits_{x \in \mathbb{R}^n } ,$ and by B(? ⁿ ) the set of all p(·) ∈ P(? ⁿ ) such that the Hardy-Littlewood maximal function M is bounded on L ^p(·)(? ⁿ ). In this paper, the authors give some characterizations of b for which \([{M_\beta },b]\) is bounded from L ^p(·)(? ⁿ ) into L ^q(·)(? ⁿ ), when p(·) ∈ P(? ⁿ ), 0 < β < n/p ₊ and 1/q(·) = 1/p(·) ? β/n with q(·)(n ? β)/n ∈ B(? ⁿ ).     

A Spanning Tree with High Degree Vertices

Let G be a connected graph, let ${X \subset V(G)}$ and let f be a mapping from X to {2, 3, . . .}. Kaneko and Yoshimoto (Inf Process Lett 73:163–165, 2000) conjectured that if |N _G (S) ? X| ≥ f (S) ? 2|S| + ω _G (S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ . In this paper, we show a result with a stronger assumption than this conjecture; if |N _G (S) ? X| ≥ f (S) ? 2|S| + α(S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ .     

Tetramodules Over a Bialgebra Form a 2-fold Monoidal Category

Let B be an associative bialgebra over any field. A module over B in the sense of deformation theory is a tetramodule over B. All tetramodules form an abelian category. This category was studied by R. Taillefer (Algebr Represent Theory 7(5):471–490, 2004) and R. Taillefer (J Algebra 276(1):259–279, 2004). In particular, she proved that for any bialgebra B, the abelian category ${{\mathcal{T}}etra}(B)$ has enough injectives, and that Ext^???(B,B) in this category coincides with the Gerstenhaber-Schack cohomology of B. We prove that the category ${{\mathcal{T}}etra}(B)$ of tetramodules over any bialgebra B is a 2-fold-monoidal category, with B a unit object in it. Roughly, this means that the category ${{\mathcal{T}}etra}(B)$ admits two monoidal structures, with common unit B, which are compatible in some rather non-trivial way (the concept of an n-fold monoidal category is introduced in Baltenu et al. (Adv Math 176:277–349, 2003)). Within (yet unproven) 2-fold monoidal analogue of the Deligne conjecture, our result would imply that RHom^???(B,B) in the category of tetramodules is naturally a homotopy 3-algebra.     

The Harish-Chandra isomorphism for reductive symmetric superpairs

We consider symmetric pairs of Lie superalgebras and introduce a graded Harish-Chandra homomorphism. Generalising results of Harish-Chandra and V. Kac, M. Gorelik, we prove that, assuming reductivity, its image is a certain explicit filtered subalgebra J( $ \mathfrak{a} $ ) of the Weyl invariants on a Cartan subspace whose associated graded gr J( $ \mathfrak{a} $ ) is the image of Chevalley’s restriction map on symmetric invariants. In contrast to the known cases, J( $ \mathfrak{a} $ ) is in general not isomorphic to gr J( $ \mathfrak{a} $ ).     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.