A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations

be a network, where is an undirected graph with nodes and edges, is a set of specified nodes of , called terminals, and each edge of has a nonnegative integer capacity . If the total capacity of edges with one end at is even for every non-terminal node , then is called inner Eulerian. A free multiflow is a collection of flows between arbitrary pairs of terminals such that the total flow through each edge does not exceed its capacity. In this paper we first generalize a method in Karzanov [11] to find a maximum integer free multiflow in an inner Eulerian network, in time, where is the complexity of finding a maximum flow between two terminals. Next we extend our algorithm to solve the so-called laminar locking problem on multiflows, also in time. We then consider analogs of the above problems in inner balanced directed networks, which means that for each non-terminal node , the sums of capacities of arcs entering and leaving are the same. We show that for such a network a maximum integer free multiflow can be constructed in time, and then extend this result to the corresponding locking problem. Received: March 24, 1997     

Orthogonal exponentials on the generalized plane Sierpinski gasket

The self-affine measure μ_Mp,D corresponding tois supported on the the generalized plane Sierpinski gasket T(M_p,D). In the present paper we show that there exist at most 3 mutually orthogonal exponential functions in L²(μ_Mp,D), and the number 3 is the best. This generalizes several known results on the non-spectral self-affine measure problem.     

The quaternionic evolution operator

In the recent years, the notion of slice regular functions has allowed the introduction of a quaternionic functional calculus. In this paper, motivated also by the applications in quaternionic quantum mechanics, see Adler (1995) [1], we study the quaternionic semigroups and groups generated by a quaternionic (bounded or unbounded) linear operator T=T₀+iT₁+jT₂+kT₃. It is crucial to note that we consider operators with components T?(?=0,1,2,3) that do not necessarily commute. Among other results, we prove the quaternionic version of the classical Hille–Phillips–Yosida theorem. This result is based on the fact that the Laplace transform of the quaternionic semigroup etT is the S-resolvent operator , the quaternionic analogue of the classical resolvent operator. The noncommutative setting entails that the results we obtain are somewhat different from their analogues in the complex setting. In particular, we have four possible formulations according to the use of left or right slice regular functions for left or right linear operators.     

Free multiflows in bidirected and skew-symmetric graphs

A graph (digraph) G=(V,E) with a set T⊆V of terminals is called inner Eulerian if each nonterminal node v has even degree (resp. the numbers of edges entering and leaving v are equal). Cherkassky and Lovász, independently, showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph G is equal to , where λ(s) is the minimum number of edges whose removal disconnects s and T-{s}. A similar relation for inner Eulerian digraphs was established by Lomonosov. Considering undirected and directed networks with “inner Eulerian” edge capacities, Ibaraki, Karzanov, and Nagamochi showed that the problem of finding a maximum integer multiflow (where partial flows connect arbitrary pairs of distinct terminals) is reduced to O(logT) maximum flow computations and to a number of flow decompositions.In this paper we extend the above max-min relation to inner Eulerian bidirected graphs and inner Eulerian skew-symmetric graphs and develop an algorithm of complexity for the corresponding capacitated cases. In particular, this improves the best known bound for digraphs. Our algorithm uses a fast procedure for decomposing a flow with O(1) sources and sinks in a digraph into the sum of one-source-one-sink flows.     

Optimal inverse Littlewood–Offord theorems

Let ηi, i=1,…,n, be iid Bernoulli random variables, taking values ±1 with probability . Given a multiset V of n integers v₁,…,vn, we define the concentration probability as A classical result of Littlewood–Offord and Erd?s from the 1940s asserts that, if the vi are non-zero, then ρ(V) is O(n−1/2). Since then, many researchers have obtained improved bounds by assuming various extra restrictions on V.About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the inverse Littlewood–Offord problem. In the inverse problem, one would like to characterize the set V, given that ρ(V) is relatively large.In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen the previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sárközy and Szemerédi and Halász.The method also applies to the continuous setting and leads to a simple proof for the β-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices.All results extend to the general case when V is a subset of an abelian torsion-free group, and ηi are independent variables satisfying some weak conditions.     

Improving multicut in directed trees by upgrading nodes

In this paper, we consider the network improvement problem for multicut by upgrading nodes in a directed tree T = (V, E) with multiple sources and multiple terminals. In a node based upgrading model, a node v can be upgraded at the expense of c(v) and such an upgrade reduces weights on all edges incident to v. The objective is to upgrade a minimum cost subset S ⊆ V of nodes such that the resulting network has a multicut in which no edge has weight larger than a given value D. We first obtain a minimum cardinality node multicut V_c for tree T, then find the minimum cost upgrading set based on the upgrading sets for the subtrees rooted at the nodes in V_c. We show that our algorithm is polynomial when the number of source–terminal pairs is upper bounded by a given value.     

Finite axiomatizability in ?ukasiewicz logic

We classify every finitely axiomatizable theory in infinite-valued propositional ?ukasiewicz logic by an abstract simplicial complex (V,Σ) equipped with a weight function ω:V→{1,2,…}. Using the W?odarczyk–Morelli solution of the weak Oda conjecture for toric varieties, we then construct a Turing computable one–one correspondence between (Alexander) equivalence classes of weighted abstract simplicial complexes, and equivalence classes of finitely axiomatizable theories, two theories being equivalent if their Lindenbaum algebras are isomorphic. We discuss the relationship between our classification and Markov’s undecidability theorem for PL-homeomorphism of rational polyhedra.     

Approximation properties and absence of Cartan subalgebra for free Araki–Woods factors

We show that all the free Araki–Woods factors Γ^″(HR,Ut) have the complete metric approximation property. Using Ozawa–Popa?s techniques, we then prove that every nonamenable subfactor N⊂Γ^″(HR,Ut) which is the range of a normal conditional expectation has no Cartan subalgebra. We finally deduce that the type III₁ factors constructed by Connes in the ?70s can never be isomorphic to any free Araki–Woods factor, which answers a question of Shlyakhtenko and Vaes.     

Hopf monads on monoidal categories

We define Hopf monads on an arbitrary monoidal category, extending the definition given in Bruguières and Virelizier (2007) [5] for monoidal categories with duals. A Hopf monad is a bimonad (or opmonoidal monad) whose fusion operators are invertible. This definition can be formulated in terms of Hopf adjunctions, which are comonoidal adjunctions with an invertibility condition. On a monoidal category with internal Homs, a Hopf monad is a bimonad admitting a left and a right antipode.Hopf monads generalize Hopf algebras to the non-braided setting. They also generalize Hopf algebroids (which are linear Hopf monads on a category of bimodules admitting a right adjoint). We show that any finite tensor category is the category of finite-dimensional modules over a Hopf algebroid.Any Hopf algebra in the center of a monoidal category C gives rise to a Hopf monad on C. The Hopf monads so obtained are exactly the augmented Hopf monads. More generally if a Hopf monad T is a retract of a Hopf monad P, then P is a cross product of T by a Hopf algebra of the center of the category of T-modules (generalizing the Radford–Majid bosonization of Hopf algebras).We show that the comonoidal comonad of a Hopf adjunction is canonically represented by a cocommutative central coalgebra. As a corollary, we obtain an extension of Sweedler?s Hopf module decomposition theorem to Hopf monads (in fact to the weaker notion of pre-Hopf monad).     

Deformations of associative submanifolds with boundary

Let M be a topological G₂-manifold. We prove that the space of infinitesimal associative deformations of a compact associative submanifold Y with boundary in a coassociative submanifold X is the solution space of an elliptic problem. For a connected boundary ∂Y of genus g, the index is given by _∫∂Yc₁(νX)+1−g, where νX denotes the orthogonal complement of T∂Y in TX|∂Y and c₁(νX) the first Chern class of νX with respect to its natural complex structure. Further, we exhibit explicit examples of non-trivial index.     

Extended Deligne–Lusztig varieties for general and special linear groups

We give a generalisation of Deligne–Lusztig varieties for general and special linear groups over finite quotients of the ring of integers in a non-archimedean local field. Previously, a generalisation was given by Lusztig by attaching certain varieties to unramified maximal tori inside Borel subgroups. In this paper we associate a family of so-called extended Deligne–Lusztig varieties to all tamely ramified maximal tori of the group.Moreover, we analyse the structure of various generalised Deligne–Lusztig varieties, and show that the “unramified” varieties, including a certain natural generalisation, do not produce all the irreducible representations in general. On the other hand, we prove results which together with some computations of Lusztig show that for SL₂(Fq???/(?²)), with odd q, the extended Deligne–Lusztig varieties do indeed afford all the irreducible representations.     

Arc-disjoint in-trees in directed graphs

Given a directed graph D = (V,A) with a set of d specified vertices S = {s ₁,…, s _d } ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ _i=1 ^d f(s _i ) arc-disjoint in-trees denoted by T _i,1,T _i,2,…, for every i = 1,…,d such that T _i,1,…, are rooted at s _i and each T _i,j spans the vertices from which s _i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case. Supported by JSPS Research Fellowships for Young Scientists. Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan.     

A generalized Turán problem in random graphs

We study a generalization of the Turán problem in random graphs. Given graphs T and H, let ex(G(n,p),T,H) be the largest number of copies of T in an H‐free subgraph of G(n,p). We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every H and every 2‐balanced T. Our results in the case when m₂(H) > m₂(T) are a natural generalization of the Erd?s‐Stone theorem for G(n,p), proved several years ago by Conlon‐Gowers and Schacht; the case T = K_m was previously resolved by Alon, Kostochka, and Shikhelman. The case when m₂(H) ≤ m₂(T) exhibits a more complex behavior. Here, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of H with copies of T and the typical value(s) of ex(G(n,p),T,H) are given by solutions to deterministic hypergraph Turán‐type problems that we are unable to solve in full generality.     

Convergence of the Dirichlet solutions of the very fast diffusion equation

For any −1<m<0, positive functions f, g and u₀≥0, we prove that under some mild conditions on f, g and u₀ as R→∞ the solution u^R of the Dirichlet problem u_t=(u^m/m)_xx in (−R,R)×(0,∞), u(R,t)=(f(t)|m|R)^1/m, u(−R,t)=(g(t)|m|R)^1/m for all t>0, u(x,0)=u₀(x) in (−R,R), converges uniformly on every compact subset of R×(0,T) to the solution of the equation u_t=(u^m/m)_xx in R×(0,T), u(x,0)=u₀(x) in R, which satisfies some mass loss formula on (0,T) where T is the maximal time such that the solution u is positive. We also prove that the solution constructed is equal to the solution constructed in Hui (2007) [15] using approximation by solutions of the corresponding Neumann problem in bounded cylindrical domains.     

The iterated Aluthge transforms of a matrix converge

Given an r×r complex matrix T, if T=U|T| is the polar decomposition of T, then, the Aluthge transform is defined byΔ(T)=|T|^1/2U|T|^1/2. Let Δn(T) denote the n-times iterated Aluthge transform of T, i.e., Δ⁰(T)=T and Δn(T)=Δ(Δn−1(T)), n∈N. We prove that the sequence {Δn(T)}_n∈N converges for every r×r matrix T. This result was conjectured by Jung, Ko and Pearcy in 2003. We also analyze the regularity of the limit function.     

Weak subintegral closure of ideals

We describe some basic facts about the weak subintegral closure of ideals in both the algebraic and complex-analytic settings. We focus on the analogy between results on the integral closure of ideals and modules and the weak subintegral closure of an ideal. We start by giving a new geometric interpretation of the Reid–Roberts–Singh criterion for when an element is weakly subintegral over a subring. We give new characterizations of the weak subintegral closure of an ideal. We associate with an ideal I of a ring A an ideal I_>, which consists of all elements of A such that v(a)>v(I), for all Rees valuations v of I. The ideal I_> plays an important role in conditions from stratification theory such as Whitney's condition A and Thom's condition Af and is contained in every reduction of I. We close with a valuative criterion for when an element is in the weak subintegral closure of an ideal. For this, we introduce a new closure operation for a pair of modules, which we call relative weak closure. We illustrate the usefulness of our valuative criterion.     

On open problems concerning distributional chaos for triangular maps

We show that in the class T of the triangular maps (x,y)?(f(x),g_x(y)) of the square there is a map of type 2^∞ with non-minimal recurrent points which is not DC3. We also show that every DC1 continuous map of a compact metric space has a trajectory which cannot be (weakly) approximated by trajectories of compact periodic sets. These two results make possible to answer some open questions concerning classification of maps in T with zero topological entropy, and contribute to an old problem formulated by A.N. Sharkovsky.     

On the Kantorovich–Rubinstein theorem

The Kantorovich–Rubinstein theorem provides a formula for the Wasserstein metric W₁ on the space of regular probability Borel measures on a compact metric space. Dudley and de Acosta generalized the theorem to measures on separable metric spaces. Kellerer, using his own work on Monge–Kantorovich duality, obtained a rapid proof for Radon measures on an arbitrary metric space. The object of the present expository article is to give an account of Kellerer’s generalization of the Kantorovich–Rubinstein theorem, together with related matters. It transpires that a more elementary version of Monge–Kantorovich duality than that used by Kellerer suffices for present purposes. The fundamental relations that provide two characterizations of the Wasserstein metric are obtained directly, without the need for prior demonstration of density or duality theorems. The latter are proved, however, and used in the characterization of optimal measures and functions for the Kantorovich–Rubinstein linear programme. A formula of Dobrushin is proved.     

Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs

We prove that every Eulerian orientation of K_m,n contains arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004