Bull-free Berge graphs are perfect

Abull is the (self-complementary) graph with verticesa, b, c, d, e and edgesab, ac, bc, bd, ce; a graphG is calledBerge if neitherG not its complement contains a chordless cycle whose length is odd and at least five. We prove that bull-free Berge graphs are perfect; a part of our argument relies on a new property of minimal imperfect graphs.This work was done while both authors were at the School of Computer Science, McGill University; support by NSERC is gratefully acknowledged.     

On the solutions of a functional equation of dhombres

Continuous solutions of the functional equation ?(x?(x)) = (?(x))² for x ∈ [0,∞) have been characterized by Dhombres. They form a simple, two-parametric family and the result can be easily extended to solutions on the whole real line. However, the class of all solutions is much larger. We show that there is a solution ? whose graph has, among others, the full outer two-dimensional Lebesgue measure. It turns out that partial restrictions, like boundedness, monotonicity and/or continuity on a subinterval do not imply the continuity of solutions. In particular, the class of monotonic solutions has interesting properties. We provide some techniques of constructing such solutions and show that, among others, there is a strictly increasing solution ? whose points of discontinuity form a dense set in R.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

A ``universal' dynamical system generated by a continuous map of the interval

In this paper we show that there is a continuous map of the interval such that any -limit set of any continuous map can be transformed by a homeomorphism to an -limit set of . Consequently, any nowhere-dense compact set and any finite union of compact intervals is a homeomorphic copy of an -limit set of .

     

Measurement-induced chaos with entangled states

The dynamics of an ensemble of identically prepared two-qubit systems is investigated which is subjected to the iteratively applied measurements and conditional selection of a typical entanglement purification protocol. The resulting dynamics exhibits strong sensitivity to initial conditions. For one class of initial states two types of islands characterize the asymptotic limit. They correspond to a separable and a fully entangled two-qubit state, respectively, and their boundaries form fractal-like structures. In the presence of incoherent noise an additional stable asymptotic cycle appears.     

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.     

Comparison of Two Techniques for Proving Nonexistence of Strongly Regular Graphs

We show that the method of counting closed walks in strongly regular graphs rules out no parameter sets other than those ruled out by the method of counting eigenvalue multiplicities.     

Distributional chaos for triangular maps

In this paper we exhibit a triangular map F of the square with the following properties: (i) F is of type 2^∞ but has positive topological entropy; we recall that similar example was given by Kolyada in 1992, but our argument is much simpler. (ii) F is distributionally chaotic in the wider sense, but not distributionally chaotic in the sense introduced by Schweizer and Smítal [Trans. Amer. Math. Soc. 344 (1994) 737]. In other words, there are lower and upper distribution functions Φ_xy and Φ_xy^* generated by F such that Φ_xy^*≡1 and Φ_xy(0₊)<1, and no distribution functions Φ_uv, and Φ_uv^* such that Φ_uv^*≡1 and Φ_uv(t)=0 whenever 0<t<ε, for some ε>0. We also show that the two notions of distributional chaos used in the paper, for continuous maps of a compact metric space, are invariants of topological conjugacy.     

Edmonds polytopes and weakly hamiltonian graphs

Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degreeconstrained subgraphs. Professor C. St. J.A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, we determine a new set of inequalities (the comb inequalities) which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the ones previously known. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the traveling salesman problem.