Ordering trees by the Laplacian coefficients

Motivated by a Mohar’s paper proposing “how to order trees by the Laplacian coefficients”, we investigate a partial ordering of trees with diameters 3 and 4 by the Laplacian coefficients. These results are used to determine several orderings of trees by the Laplacian coefficients.     

Counting strings in Dyck paths

This paper deals with the enumeration of Dyck paths according to the statistic “number of occurrences of τ”, for an arbitrary string τ. In this direction, the statistic “number of occurrences of τ at height j” is considered. It is shown that the corresponding generating function can be evaluated with the aid of Chebyshev polynomials of the second kind. This is applied to every string of length 4. Further results are obtained for the statistic “number of occurrences of τ at even (or odd) height”.     

The enriched Vietoris monad on representable spaces

Employing a formal analogy between ordered sets and topological spaces, over the past years we have investigated a notion of cocompleteness for topological, approach and other kind of spaces. In this new context, the down-set monad becomes the filter monad, cocomplete ordered set translates to continuous lattice, distributivity means disconnectedness, and so on. Curiously, the dual(?) notion of completeness does not behave as the mirror image of the one of cocompleteness; and in this paper we have a closer look at complete spaces. In particular, we construct the “up-set monad” on representable spaces (in the sense of L. Nachbin for topological spaces, respectively C. Hermida for multicategories); we show that this monad is of Kock–Zöberlein type; we introduce and study a notion of weighted limit similar to the classical notion for enriched categories; and we describe the Kleisli category of our “up-set monad”. We emphasise that these generic categorical notions and results can be indeed connected to more “classical” topology: for topological spaces, the “up-set monad” becomes the lower Vietoris monad, and the statement “X   is totally cocomplete if and only if X^op$X^{\mathrm{op}}$ is totally complete” specialises to O. Wyler's characterisation of the algebras of the Vietoris monad on compact Hausdorff spaces as precisely the continuous lattices.     

Vertex-weightings for distance moments and thorny graphs

Valence-weightings are considered for shortest-path distance moments, as well as related weightings for the so-called “Wiener” polynomial. In the case of trees the valence-weighted quantities are found to be expressible as a combination of unweighted quantities. Further the weighted quantities for a so-called “thorny” graph are considered and shown to be related to the weighted and unweighted quantities for the underlying parent graph.     

A new bound for neighbor-connectivity of abelian Cayley graphs

For the notion of neighbor-connectivity in graphs, whenever a vertex is “subverted” the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. The main result of this paper is a sharpening of the bound for abelian Cayley graphs. In particular, we show by constructing an effective subversion strategy for such graphs, that neighbor-connectivity is bounded above by ⌈δ/2⌉+2. Using a result of Watkins the new bound can be recast in terms of κ to get neighbor-connectivity bounded above by ⌈3κ/4⌉+2 for abelian Cayley graphs.     

Selecting non-zero weights to evaluate effectiveness of basketball players with DEA

In this paper, we show how DEA may be used to identify component profiles as well as overall indices of performance in the context of an application to assessments of basketball players. We go beyond the usual uses of DEA to provide only overall indexes of performance. Our focus is, instead, on the multiplier values for the efficiently rated players. For this purpose we use a procedure that we recently developed that guarantees a full profile of non-zero weights, or “multipliers.” We demonstrate how these values can be used to identify relative strengths and weaknesses in individual players. Here we also utilize the flexibility of DEA by introducing bounds on the allowable values to reflect the views of coaches, trainers and other experts on the basketball team for which evaluations are being conducted. Finally we show how these combinations can be extended by taking account of team as well as individual considerations.     

On the stability of the Serrin problem

We investigate stability issues concerning the radial symmetry of solutions to Serrin's overdetermined problems. In particular, we show that, if u is a solution to Δu=n in a smooth domain Ω⊂Rn, u=0 on ∂Ω and |Du| is “close” to 1 on ∂Ω, then Ω is “close” to the union of a certain number of disjoint unitary balls.     

Patching upX-trees

A fundamental problem in many areas of classification, and particularly in biology, is the reconstruction of a leaf-labeled tree from just a subset of its induced subtrees. Without loss of generality, we may assume that these induced subtrees all have precisely four leaves. Of particular interest is determining whether a collection of quartet subtrees uniquely defines a parent tree. Here, we solve this problem in the case where the collection of quartet trees is of minimal size, by studyingencodings of binary trees by such quartet trees. We obtain a characterization of minimal encodings that exploits an underlying patchwork structure. As we will show elsewhere, this allows one to obtain a polynomial time algorithm for certain instances of the problem of reconstructing trees from subtrees.Supported by DFG — Graduiertenkolleg Strukturbildungsprozesse, Forschungsschwerpunkt Mathematisierung, University of Bielefeld, Germany.Supported by the New Zealand Marsden Fund.     

Sampling per mode for rare event simulation in switching diffusions

A straightforward application of an interacting particle system to estimate a rare event for switching diffusions fails to produce reasonable estimates within a reasonable amount of simulation time. To overcome this, a conditional “sampling per mode” algorithm has been proposed by Krystul in [10]; instead of starting the algorithm with particles randomly distributed, we draw in each mode, a fixed number particles and at each resampling step, the same number of particles is sampled for each visited mode. In this paper, we establish a law of large numbers as well as a central limit theorem for the estimate.     

How not to characterize planar-emulable graphs

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)—a problem raised already in Fellows? thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami?s conjecture—which is still open—as the two were considered equivalent. But, at the end of 2008, a surprising construction by Rieck and Yamashita falsified the natural “planar emulator conjecture”, and thus opened a whole new research field. We present further results and constructions which show how far the planar-emulability concept is from planar-coverability, and that the traditional idea of likening it to projective embeddability is actually very out-of-place. We also present several positive partial characterizations of planar-emulable graphs.     

Almost equal group multiplications

In a recent paper entitled “A commutative analogue of the group ring” we introduced, for each finite group (G,⋅), a commutative graded Z-algebra R_(G,⋅) which has a close connection with the cohomology of (G,⋅). The algebra R_(G,⋅) is the quotient of a polynomial algebra by a certain ideal I_(G,⋅) and it remains a fundamental open problem whether or not the group multiplication ⋅ on G can always be recovered uniquely from the ideal I_(G,⋅).Suppose now that (G,×) is another group with the same underlying set G and identity element e∈G such that I_(G,⋅)=I_(G,×). Then we show here that the multiplications ⋅ and × are at least “almost equal” in a precise sense which renders them indistinguishable in terms of most of the standard group theory constructions. In particular in many cases (for example if (G,⋅) is Abelian or simple) this implies that the two multiplications are actually equal as was claimed in the previously cited paper.     

Duality in coherent configurations

By introducing a duality operator in coherent algebras (i.e. adjacency algebras of coherent configurations) we give a new interpretation to Delsarte's duality theory for association schemes. In particular we show that nonnegative matrices and positive semidefinite matrices, (0, 1)-matrices and distance matrices, regular graphs and spherical 2-designs, distance regular graphs and Delsarte matricesare pairs of dual objects. Several almost dual properties which are not yet fully understood are also reported.     

Cantor families of periodic solutions for wave equations via a variational principle

We prove existence of small amplitude periodic solutions of completely resonant wave equations with frequencies in a Cantor set of asymptotically full measure, via a variational principle. A Lyapunov-Schmidt decomposition reduces the problem to a finite dimensional bifurcation equation—variational in nature—defined on a Cantor set of non-resonant parameters. The Cantor gaps are due to “small divisors” phenomena. To solve the bifurcation equation we develop a suitable variational method. In particular, we do not require the typical “Arnold non-degeneracy condition” of the known theory on the nonlinear terms. As a consequence our existence results hold for new generic sets of nonlinearities.     

The Topological Tverberg Theorem and winding numbers

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d?1, and if q is a prime power, but not yet in general.)The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a “Winding Number Conjecture” that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to R^d. “Many Tverberg partitions” arise if and only if there are “many q-winding partitions.”The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_3q-2 in the plane. We investigate graphs that are minimal with respect to the winding number condition.     

Call routing and the ratcatcher

Suppose we expect there to bep(ab) phone calls between locationsa andb, all choices ofa, b from some setL of locations. We wish to design a network to optimally handle these calls. More precisely, a routing tree is a treeT with set of leavesL, in which every other vertex has valency 3. It has congestion <k if for every edgee ofT, there are fewer thank calls which will be routed alonge, that is, between locationa, b in different components ofT/e. Deciding if there is a routing tree with congestion <k is NP-hard, but if the pairsab, withp(ab)>0 form the edges of a planar graphG, there is an efficient, strongly polynomial algorithm.This is because the problem is equivalent to deciding if a ratcatcher can corner a rat loose in the walls of a house with floor planG, wherep(ab) is a thickness of the wallab. The ratcatcher carries a noisemaker of powerk, and the rat will not move through any wall in which the noise level is too high (determined by the total thickness of the intervening walls between this one and the noisemaker).It follows that branch-width is polynomially computable for planar graphs—that too is NP-hard for general graphs.This research was performed under a consulting agreement with Bellcore.     

A Dynamic location problem for graphs

We introduce a class of optimization problems, calleddynamic location problems, involving the processing of requests that occur sequentially at the nodes of a graphG. This leads to the definition of a new parameter of graphs, called the window indexWX(G), that measures how large a window into the future is needed to solve every instance of the dynamic location problem onG optimally on-line. We completely characterize this parameter:WX(G)k if and only ifG is a weak retract of a product of complete graphs of size at mostk. As a byproduct, we obtain two (polynomially recognizable) structural characterizations of such graphs, extending a result of Bandelt.     

Minimal imperfect graphs: A simple approach

We provide a very short proof of the following theorem of Lovász, and of its consequences:A graph is perfect if and only if in every induced subgraph the number of vertices does not exceed the product of the stability and clique numbers of the subgraph.This proof is conceptually new: it does not use the replication operation, or any kind of polyhedral argument; the arguments resemble more the well-known ways of deducing structural properties of minimal imperfect graphs. However, the known proofs of these structural properties use Lovász's result, whereas the present work leads to a proof of Lovász's result itself, and actually to a slight sharpening.The author gratefully acknowledges financial support from Ministère de la Recherche et de la Technologie (the French Ministry of Research and Technology, MRT) which sponsored his three month visit to Laboratory ARTEMIS of Grenoble University which motivated him to do this work.     

Some recollections on early work with Jan Pelant

In this note we consider three questions which can be traced to our early collaboration with Jan “Honza” Pelant. We present them from the contemporary perspective, in some cases extending our earlier work. The questions relate to Ramsey theory, uniform spaces and tournaments.