Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

Proportions of Irreducible Diagrams

We investigate the proportion of graphs on n-vertices each of which is m-valent, that are “k-reducible”. An asymptotic formula is developed for large n and fixed values of the other variables, in terms of an n-independent parameter that is evaluated for a number of (m, k) values.     

Ancestors and descendants in evolving k‐tree models

We consider several random graph models based on k‐trees, which can be generated by applying the probabilistic growth rules “uniform attachment”, “preferential attachment”, or a “saturation”‐rule, respectively, but which also can be described in a combinatorial way. For all of these models we study the number of ancestors and the number of descendants of nodes in the graph by carrying out a precise analysis which leads to exact and limiting distributional results. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 465–489, 2014     

Generalized Rotation numbers

A rooted graph is a pair (G,x), where G is a simple undirected graph and x ∈ V(G). If G is rooted at x, its kth rotation number h_k (G,x) is the minimum number of edges in a graph F of order |G| + k such that for every v ∈ V(F) we can find a copy of G in F with the root vertex x at v. When k = 0, this definition reduces to that of the rotation number h(G,x), which was introduced in [“On Rotation Numbers for Complete Bipartite Graphs,” University of Victoria, Department of Mathematics Report No. DM-186-IR (1979)] by E.J. Cockayne and P.J. Lorimer and subsequently calculated for complete multipartite graphs. In this paper, we estimate the kth rotation number for complete bipartite graphs G with root x in the larger vertex class, thereby generalizing results of B. Bollobás and E.J. Cockayne [“More Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory, Vol. 6 (1982), pp. 403–411], J. Haviland [“Cliques and Independent Sets,” Ph. D. thesis, University of Cambridge (1989)], and J. Haviland and A. Thomason [“Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory, Vol. 16 (1992), pp. 61–71]. © 1993 John Wiley & Sons, Inc.     

Projections of the Aldous chain on binary trees: Intertwining and consistency

Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k<n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k‐tree with total mass n.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k‐trees evolve as Markov chains themselves, and are projectively consistent over k. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n→∞ continuum analog of the Aldous chain and will be taken up elsewhere.     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

Non-recursive functions,knots “with thick ropes,” and self-clenching “thick” hyperspheres

We introduce an approach to certain geometric variational problems based on the use of the algorithmic unrecognizability of the n-dimensional sphere for n ≥ 5. Sometimes this approach allows one to prove the existence of infinitely many solutions of a considered variational problem. This recursion-theoretic approach is applied in this paper to a class of functionals on the space of C^1.1-smooth hypersurfaces diffeomorphic to Sⁿ in Rⁿ⁺¹, where n is any fixed number ≥ 5. The simplest of these functionals k_v is defined by the formula k_v(Σⁿ) = (vol(Σⁿ))^1/n/r(Σⁿ), where r(Σⁿ) denotes the radius of injectivity of the normal exponential map for Σⁿ ? Rⁿ+l. We prove the existence of an infinite set of distinct locally minimal values of k_v on the space of C^1.1-smooth topological hyperspheres in Rⁿ⁺¹ for any n ≥ 5. The functional k_v naturally arises when one attempts to generalize knot theory in order to deal with embeddings and isotopies of “thick” circles and, more generally, “thick” spheres into Euclidean spaces. We introduce the notion of knot “with thick rope” types. The theory of knot “with thick rope” types turns out to be quite different from the classical knot theory because of the following result: There exists an infinite set of non-trivial knot “with thick rope” types in codimension one for every dimension greater than or equal to five.     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

Decompositions and reductions of snarks

According to M. Gardner [“Mathematical Games: Snarks, Boojums, and Other Conjectures Related to the Four-Color-Map Theorem,” Scientific American, vol. 234 (1976), pp. 126–130], a snark is a nontrivial cubic graph whose edges cannot be properly colored by three colors. The problem of what “nontrivial” means is implicitly or explicitly present in most papers on snarks, and is the main motivation of the present paper. Our approach to the discussion is based on the following observation. If G is a snark with a k-edge-cut producing components G₁ and G₂, then either one of G₁ and G₂ is not 3-edge-colorable, or by adding a “small” number of vertices to either component one can obtain snarks G₁ and G₂ whose order does not exceed that of G. The two situations lead to a definition of a k-reduction and k-decomposition of G. Snarks that for m < k do not admit m-reductions, m-decompositions, or both are k-irreducible, k-indecomposable, and k-simple, respectively. The irreducibility, indecomposability, and simplicity provide natural measures of nontriviality of snarks closely related to cyclic connectivity. The present paper is devoted to a detailed investigation of these invariants. The results give a complete characterization of irreducible snarks and characterizations of k-simple snarks for k ≤ 6. A number of problems that have arisen in this research conclude the paper. © 1996 John Wiley & Sons, Inc.     

On a variation of the Oberwolfach problem

We consider the following “spouse-avoiding” variant of the Oberwolfach problem (briefly NOP): “At a gathering there are n couples. Is it possible to arrange a seating for the 2n people present at s round tables T₁,T₂,…,T_s (where T_i can accomodate k_i ? 3 people and Σk_i=2n) for m different meals so that each person has every other person except his spouse for a neighbour exactly once?” We prove several results concerning the existence of solutions to NOP. In particular, we settle the cases when the tables accomodate the same “small” number of people or when there are only two tables one of them accomodating a “small” number of people or when the total number of people is “small”.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Weak Covering at Large Cardinals

We show that weakly compact cardinals are the smallest large cardinals k where k⁺ < k⁺ is impossible provided 0^# does not exist. We also show that if k^+Kc < k⁺ for some k being weakly compact (where K^c is the countably complete core model below one strong cardinal), then there is a transitive set M with M ? ZFC + “there is a strong cardinal”.     

Counting colorful multi-dimensional trees

LetV be a disjoint union ofr finite setsV ₁,...,V _r (colors). A collectionT of subsets ofV iscolorful if each member ifT contains at most one point of each color. Ak-dimensional colorful tree is a colorful collectionT of subsets ofV, each of sizek+1, such that if we add toT all the colorful subsets ofV of sizek or less, we get aQ-acyclic simplicial complex _T We count (using the Binet-Cauchy theorem) thek-dimensional colorful trees onV (for allk), where each treeT is counted with weight . The result confirms, in a way, a formula suggested by Bolker. (fork-r–1). It extends, on one hand, a result of Kalai on weighted counting ofk-dimensional trees and, on the other hand, enumeration formulas for multi-partite (1-dimensional) trees. All these results are extensions of Cayley's celebrated treecounting formula, now 100 years old.     

Forcing the Least Measurable to Violate GCH

Starting with a model for “GCH + k is k⁺ supercompact”, we force and construct a model for “k is the least measurable cardinal + 2^k = K⁺”. This model has the property that forcing over it with Add(k,k⁺⁺) preserves the fact k is the least measurable cardinal.     

The Cardinality of Sets of k -Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes.     

Parsimonious phylogenetic trees in metric spaces and simulated annealing

Steiner trees for (finite) subsets D of metric spaces S are discussed. For a given (abstract) tree topology over D Steiner interpretations in S are defined and their properties are studied. An algorithm to obtain Steiner interpretations for a given tree topology is given which is efficient if S is the (L₁-) product of small metric spaces, e.g., if S is the sequence space A^l over an alphabet A of small cardinality. A variant of the same algorithm can be used to minimize efficiently and exactly spin glass Hamiltonians of k-meshed graphs. The interpretation algorithm is used as an ingredient for a variant of the stochastic search algorithm called “simulated annealing” which is used to find Steiner trees for various given data sets D in various sequence spaces S = A^l. For all data sets analyzed so far the trees obtained this way are shorter than or at least as short as the best ones derived using other tree construction methods. Two main features can be observed:

• 1.(1) Very often the shape of Steiner trees constructed this way is more or less chain-like. The trees are “long and slim.”
• 2.(2) Generally, the method allows to find many different Steiner trees.

As a consequence, one may conclude that tree reconstruction programs should be executed in an interactive fashion so that additional biological knowledge, not explicitly represented in the data set, can be introduced at various stages of the reconstruction algorithm to reduce the number of possible solutions. Moreover, as the “Simulated Annealing” search procedure is universally applicable, one may also use this algorithm during such an interactive reconstruction program to optimize any other of the known tree reconstruction minimality principles.     

Automatic Optimal Regularization for Ill-Posed Problems with Stochastical Noise without Imposing Smoothness Assumptions

We consider the compact operator A : 𝒳 → 𝒴 for the separable Hilbert spaces 𝒳 and 𝒴. The problem Ax = y is called ill-posed when the singular values s_k , k = 1, 2, … of the operator A tend to zero. Classically one assumes that y is biased with “deterministic noise”; we will also consider “stochastic noise” where the noise element is a weak Gaussian random variable. There classical stopping rules (e.g. Morozov) do not work. We will show that both for the “deterministic noise” case as well for the “stochastical noise” case we can regularize in an (asymptotically almost) optimal way without knowledge of the smoothness of the solution using Lepskij's method. Furthermore the method also works for estimated error levels and error behavior. So we can assure regularization which is just dependent on measurements obtainable in reality, e.g. satellite problems. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Automorphisms on Catalan trees and bracketings

Two mirror-image isomorphisms between general bracketings and binary bracketings are formalized which parallel the isomorphisms described by De Bruijn and Morselt between plane trees and trivalent plane trees. These maps lead to automorphisms on these four Catalan families. It is found that the orbit structure of these automorphisms is determined by certain “primitive” elements of the four families, and that the enumerator p_n of these primitive elements satisfies the equations: p_n = m_n?2 + m_n?1, where m_n = Σ_k=0 (_2kⁿ)c_k, c_n the Catalan numbers, and

It is then shown that these automorphisms yield isomorphisms between several interesting subsets of the trees and brackets, most of them enumerated by m_n. In particular, it is shown that the general bracketings containing no occurrence of “(g)(g)(g)” and those containing no occurrence of “((g))” are mapped to each other.     

The number of spanning trees in regular graphs

Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}ⁿ. where 0 ≤ δ(G) ≤ ?(k).     

The Cardinality of Sets of <Emphasis Type="Italic">k</Emphasis>-Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. Supported, in part by grants EP/C000285, NSF-DMS-0439734 and NSF-DMS-0555839. S. B. Damelin thanks the Institute for Mathematics and Applications for their hospitality.