On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

On the set of periodic intervals of an interval map

We investigate the closure of the set of periodic closed intervals for a continuous interval map with respect to Hausdorff metric. We prove that if a nondegenerate interval is limit of periodic ones then either a) it is periodic itself, or b) it is asymptotically degenerate, i.e. its diameter tends to 0 (when iterating under f). We present a continuous interval map for which case b) is possible.     

An improved bound for disjoint directed cycles

We show that every directed graph with minimum out-degree at least $18k$ contains at least $k$ vertex disjoint cycles. This is an improvement over the result of Alon who showed this result for digraphs of minimum out-degree at least $64k$. The main benefit of the argument is that getting better results for small values of $k$ allows for further improvements to the constant.     

NoteA 16-vertex tournament for which Banks set and Slater set are disjoint

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T; a Slater winner of T is the first vertex of any transitive tournament at minimum distance of T (the distance being the number of arcs to reverse in T to make T transitive). In this note, we show that there exists a tournament with 16 vertices for which no Slater winner is a Banks winner. This counterexample improves the previous one, due to G. Laffond and J.-F. Laslier, which has 75 vertices.     

Douglas algebras which are invariant under the Bourgain map

Part of this work was done while the second author was visiting the University of Georgia, Athens/Georgia, USA.     

On the problem of finding disjoint cycles and dicycles in a digraph

We study the following problem: Given a digraph D, decide if there is a cycle B in D and a cycle C in its underlying undirected graph UG(D) such that V (B)??V (C)=?. Whereas the problem is NP-complete if, as additional part of the input, a vertex x is prescribed to be contained in C, we prove that one can decide the existence of B,C in polynomial time under the (mild) additional assumption that D is strongly connected. Our methods actually find B,C in polynomial time if they exist. The behaviour of the problem as well as our solution depend on the cycle transversal number ?? (D) of D, i.e. the smallest cardinality of a set T of vertices in D such that D-T is acyclic: If ?? (D)??3 then we employ McCuaig??s framework on intercyclic digraphs to (always) find these cycles. If ?? (D) = 2 then we can characterize the digraphs for which the answer is ??yes?? by using topological methods relying on Thomassen??s theorem on 2-linkages in acyclic digraphs. For the case ?? (D)??1 we provide an algorithm independent from any earlier work.     

On the cycle map for torsion algebraic cycles of codimension two

Oblatum 7-XI-1990 &; 25-III-1991     

Entropy of random chaotic interval map with noise which causes coarse-graining

A random chaotic interval map with noise which causes coarse-graining induces a finite-state Markov chain. For a map topologically conjugate to a piecewise-linear map with the Lebesgue measure being ergodic, we prove that the Shannon entropy for the induced Markov chain possesses a finite limit as the noise level tends to zero. In most cases, the limit turns out to be strictly greater than the Lyapunov exponent of the original map without noise.     

On a family of singular continuous measures related to the doubling map

Here, we study some measures that can be represented by infinite Riesz products of 1-periodic functions and are related to the doubling map. We show that these measures are purely singular continuous with respect to Lebesgue measure and that their distribution functions satisfy super-polynomial asymptotics near the origin, thus providing a family of extremal examples of singular measures, including the Thue–Morse measure.     

Estimating Mahler measures using periodic points for the doubling map

The Mahler measure m(P)$m\left(P\right)$ of a polynomial P$P$ is a numerical value which is useful in number theory, dynamical systems and geometry. In this article we show how this can be written in terms of periodic points for the doubling map on the unit interval. This leads to an interesting algorithm for approximating m(P)$m\left(P\right)$ which we illustrate with several examples.     

Vertex‐disjoint cycles of length at most four each of which contains a specified vertex*

We obtain a sharp minimum degree condition δ (G) ≥ of a graph G of order n ≥ 3k guaranteeing that, for any k distinct vertices, G contains k vertex‐disjoint cycles of length at most four each of which contains one of the k prescribed vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 37–47, 2001     

On sums which are powers

The cardinality of sets A is estimated under the conditions that every element of the sum set A+A is a power resp. powerful number (n is said to be powerful if p n implies p ² n). Subset sums with these properties are also studied. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the disjoint paths problem

Using flow and matching algorithms to solve the problem of finding disjoint paths through a given node, and with a technique of Chekuri and Khanna, we give an approximation for the edge-disjoint paths problem in undirected graphs, directed acyclic graphs and directed graphs with edge capacity at least 2.