Capacity inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow \(x^0\), the inverse minimum cost flow problem is to modify the capacity vector or the cost vector as little as possible to make \(x^0\) form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the capacity inverse minimum cost flow problems under the weighted Hamming distance, where we use the weighted Hamming distance to measure the modification of the arc capacities. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in \(O(n\cdot m^2)\) time.     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

On trees with total domination number equal to edge-vertex domination number plus one

An edge e∈E(G) dominates a vertex v∈V(G) if e is incident with v or e is incident with a vertex adjacent to v. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is edge-vertex dominated by an edge of D. The edge-vertex domination number of a graph G is the minimum cardinality of an edge-vertex dominating set of G. A subset D?V(G) is a total dominating set of G if every vertex of G has a neighbor in D. The total domination number of G is the minimum cardinality of a total dominating set of G. We characterize all trees with total domination number equal to edge-vertex domination number plus one.     

Lower bounds on the signed total k-domination number of graphs

Let G be a graph with vertex set V(G). For any integer k ≥ 1, a signed total k-dominating function is a function f: V(G) → {?1, 1} satisfying ∑_x∈N(v)f(x) ≥ k for every v ∈ V(G), where N(v) is the neighborhood of v. The minimum of the values ∑_v∈V(G)f(v), taken over all signed total k-dominating functions f, is called the signed total k-domination number. In this note we present some new sharp lower bounds on the signed total k-domination number of a graph. Some of our results improve known bounds.     

Largest <Emphasis Type="Italic">H</Emphasis>-eigenvalue of uniform <Emphasis Type="Italic">s</Emphasis>-hypertrees

The k-uniform s-hypertree G = (V,E) is an s-hypergraph, where 1 ≤ s ≤ k - 1; and there exists a host tree T with vertex set V such that each edge of G induces a connected subtree of T. In this paper, some properties of uniform s-hypertrees are establised, as well as the upper and lower bounds on the largest H-eigenvalue of the adjacency tensor of k-uniform s-hypertrees in terms of the maximal degree Δ. Moreover, we also show that the gap between the maximum and the minimum values of the largest H-eigenvalue of k-uniform s-hypertrees is just Θ(Δ ^s/k ).     

Factorization of Lipschitzian Elements

A lipschitzian element a is given in a Clifford algebra C?(V, q) over a field K that contains at least three scalars. Here we prove that, if a is not in the subalgebra generated by a totally isotropic subspace of V, then it is a product of linearly independent vectors of V. An effective algorithm is proposed to decompose a into such a product of vectors.     

Existence and concentration behavior of sign-changing solutions for quasilinear Schrödinger equations

We consider the quasilinear Schrödinger equations of the form ?ε²Δu + V(x)u ? ε²Δ(u²)u = g(u), x∈ R^N, where ε > 0 is a small parameter, the nonlinearity g(u) ∈ C¹(R) is an odd function with subcritical growth and V(x) is a positive Hölder continuous function which is bounded from below, away from zero, and inf_ΛV(x) < inf?_ΛV(x) for some open bounded subset Λ of R^N. We prove that there is an ε₀ > 0 such that for all ε ∈ (0, ε₀], the above mentioned problem possesses a sign-changing solution uε which exhibits concentration profile around the local minimum point of V(x) as ε → 0⁺.     

<Emphasis Type="Italic">V</Emphasis>-Gorenstein injective modules preenvelopes and related dimension

Let R and S be associative rings and _S V _R a semidualizing (S-R)-bimodule. An R-module N is said to be V-Gorenstein injective if there exists a Hom _R (I _V (R),?) and Hom _R (?,I _V (R)) exact exact complex \( \cdots \to {I_1}\xrightarrow{{{d_0}}}{I_0} \to {I^0}\xrightarrow{{{d_0}}}{I^1} \to \cdots \) of V-injective modules I _i and I ⁱ , i ∈ N₀, such that N ? Im(I ₀ → I ⁰). We will call N to be strongly V-Gorenstein injective in case that all modules and homomorphisms in the above exact complex are equal, respectively. It is proved that the class of V-Gorenstein injective modules are closed under extension, direct summand and is a subset of the Auslander class A _V (R) which leads to the fact that V-Gorenstein injective modules admit exact right I _V (R)-resolution. By using these facts, and thinking of the fact that the class of strongly V-Gorenstein injective modules is not closed under direct summand, it is proved that an R-module N is strongly V-Gorenstein injective if and only if N ⊕ E is strongly V-Gorenstein injective for some V-injective module E. Finally, it is proved that an R-module N of finite V-Gorenstein injective injective dimension admits V-Gorenstein injective preenvelope which leads to the fact that, for a natural integer n, Gorenstein V-injective injective dimension of N is bounded to n if and only if \(Ext_{{I_V}\left( R \right)}^{ \geqslant n + 1}\left( {I,N} \right) = 0\) for all modules I with finite I _V (R)-injective dimension.     

Connecting orbits near the adiabatic limit of Lagrangian systems with turning points

We consider a natural Lagrangian system defined on a complete Riemannian manifold being subjected to action of a time-periodic force field with potential U(q, t, ε) = f(εt)V(q) depending slowly on time. It is assumed that the factor f(τ) is periodic and vanishes at least at one point on the period. Let X _c denote a set of isolated critical points of V(x) at which V(x) distinguishes its maximum or minimum. In the adiabatic limit ε → 0 we prove the existence of a set E _h such that the system possesses a rich class of doubly asymptotic trajectories connecting points of X _c for ε ∈ E _h .     

Restrained Domination in Claw-Free Graphs with Minimum Degree at Least Two

Let G = (V, E) be a graph. A set \({S\subseteq V}\) is a restrained dominating set if every vertex in V ? S is adjacent to a vertex in S and to a vertex in V ? S. The restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is claw-free with minimum degree at least two and \({G\notin \{C_{4},C_{5},C_{7},C_{8},C_{11},C_{14},C_{17}\}}\) , then \({\gamma_{r}(G)\leq \frac{2n}{5}.}\)     

On judicious bipartitions of graphs

For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V ₁?V ₂ such that G has at most s edges with both incident vertices in V _i . Alon proved that the limsup of \(f\left( m \right) - \left( {m/2 + \sqrt {m/8} } \right)\) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of \(m/4 + \left( {\sqrt {m/32} - g(m)} \right)\) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k.     

Metric extension operators,vertex sparsifiers and Lipschitz extendability

We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k/ log log k) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log²k/ log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomialtime algorithm for finding optimal operators.     

Desingularizations of Schubert varieties in double Grassmannians

Let X = Gr(k, V) × Gr(l, V) be the direct product of two Grassmann varieties of k-and l-planes in a finite-dimensional vector space V, and let B ? GL(V) be the isotropy group of a complete flag in V. We consider B-orbits in X, which are an analog of Schubert cells in Grassmannians. We describe this set of orbits combinatorially and construct desingularizations for the closures of these orbits, similar to the Bott-Samelson desingularizations for Schubert varieties.     

A continuation method for solving symmetric Toeplitz systems

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm.     

Total [1,2]-domination in Graphs

A subset S ? V in a graph G = (V,E) is a total [1, 2]-set if, for every vertex \( \upsilon \in V, 1 \leq\mid N (\upsilon)\cap S\mid\leq \). The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted by γ_t[1,2](^G).We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover, we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total [1, 2]-domination number, [1, 2]-domination number and domination number.     

Sign-changing Solutions for a Schrödinger Equation with Saturable Nonlinearity

We consider the nonlinear Schrödinger equation

$-\Delta{u} + V (x)u = K(x)u^3/(1 + u^2)$

in \({\mathbb {R}^N}\) , and assume that V and K are invariant under an orthogonal involution. Moreover, V and K converge to positive constants V _∞ and K _∞, as |x| → ∞. We present some results on the existence of a particular type of sign changing solution, which changes sign exactly once. The basic tool employed here is the Concentration–Compactness Principle and the interaction between translated solutions of the corresponding autonomous problem.

     

Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p _k of heads, and the goal is to simulate a coin flip with probability C ₁ p ₁+? + C _k p _k of heads.     

Knauf’s degree and monodromy in planar potential scattering

We consider Hamiltonian systems on (T*?², dq ∧ dp) defined by a Hamiltonian function H of the “classical” form H = p ²/2 + V(q). A reasonable decay assumption V(q) → 0, ‖q‖ → ∞, allows one to compare a given distribution of initial conditions at t = ?∞ with their final distribution at t = +∞. To describe this Knauf introduced a topological invariant deg(E), which, for a nontrapping energy E > 0, is given by the degree of the scattering map. For rotationally symmetric potentials V(q) = W(‖q‖), scattering monodromy has been introduced independently as another topological invariant. In the present paper we demonstrate that, in the rotationally symmetric case, Knauf’s degree deg(E) and scattering monodromy are related to one another. Specifically, we show that scattering monodromy is given by the jump of the degree deg(E), which appears when the nontrapping energy E goes from low to high values.     

Global existence of real roots and random Newton flow algorithm for nonlinear system of equations

To solve nonlinear system of equation, F(x) = 0, a continuous Newton flow x _t (t) = V (x) = ?(DF(x))^?1 F(x), x(0) = x ⁰ and its mathematical properties, such as the central field, global existence and uniqueness of real roots and the structure of the singular surface, are studied. We concisely introduce random Newton flow algorithm (NFA) for finding all roots, based on discrete Newton flow x ^j+1 = x ^j + hV (x ^j ) with random initial value x ⁰ and h ∈ (0, 1], and three computable quantities, g _j , d _j and K _j . The numerical experiments with dimension n = 300 are provided.     

DISTINGUISHED PRE-NICHOLS ALGEBRAS

We formally define and study the distinguished pre-Nichols algebra \( \tilde{B} \)(V) of a braided vector space of diagonal type V with finite-dimensional Nichols algebra B(V). The algebra \( \tilde{B} \)(V) is presented by fewer relations than B(V), so it is intermediate between the tensor algebra T(V) and B(V). Prominent examples of distinguished pre-Nichols algebras are the positive parts of quantized enveloping (super)algebras and their multiparametric versions. We prove that these algebras give rise to new examples of Noetherian pointed Hopf algebras of finite Gelfand-Kirillov dimension. We investigate the kernel (in the sense of Hopf algebras) of the projection from \( \tilde{B} \)(V) to B(V), generalizing results of De Concini and Procesi on quantum groups at roots of unity.