A short proof that N 3 is not a circle containment order

A partially ordered set P is called a circle containment order provided one can assign to each xP a circle C _x so that . We show that the infinite three-dimensional poset N ³ is not a circle containment order and note that it is still unknown whether or not [n]³ is such an order for arbitrarily large n.     

New constructions for De Bruijn tori

A De Bruijn torus is a periodicd-dimensionalk-ary array such that eachn ₁ × ... ×n _d k-ary array appears exactly once with the same period. We describe two new methods of constructing such arrays. The first is a type of product that constructs ak ₁ k ₂ -ary torus from ak ₁ -ary torus and ak ₂ -ary torus. The second uses a decomposition of ad-dimensional torus to produce ad+1 dimensional torus. Both constructions will produce two dimensionalk-ary tori for which the period is not a power ofk. In particular, for and for all natural numbers (n ₁ , n ₂ ), we construct 2-dimensionalk-ary De Bruijn tori with order n ₁ , n ₂ and period where .Dedicated to the memory of Tony BrewsterPartially supported by NSF grant DMS-9201467Partially supported by a grant from the Reidler Foundation     

Overlap Cycles for Steiner Quadruple Systems

Steiner quadruple systems are set systems in which every triple is contained in a unique quadruple. It is well known that Steiner quadruple systems of order v, or SQS(v), exist if and only if . Universal cycles, introduced by Chung, Diaconis, and Graham in 1992, are a type of cyclic Gray code. Overlap cycles are generalizations of universal cycles that were introduced in 2010 by Godbole, et al. Using Hanani's SQS constructions, we show that for every with there exists an SQS(v) that admits a 1‐overlap cycle.     

1-Overlap cycles for Steiner triple systems

A number of applications of Steiner triple systems (e.g. disk erasure codes) exist that require a special ordering of its blocks. Universal cycles, introduced by Chung, Diaconis, and Graham in 1992, and Gray codes are examples of listing elements of a combinatorial family in a specific manner, and Godbole invented the following generalization of these in 2010. 1-overlap cycles require a set of strings to be ordered so that the last letter of one string is the first letter of the next. In this paper, we prove the existence of 1-overlap cycles for automorphism free Steiner triple systems of each possible order. Since Steiner triple systems have the property that each block can be represented uniquely by a pair of points, these 1-overlap cycles can be compressed by omitting non-overlap points to produce rank two universal cycles on such designs, expanding on the results of Dewar.     

Possibility and consequences of T violation in nucleon decay

It is argued that superunified theories suggest that T violation in nucleon decay might be less well hidden than it is in ordinary weak interactions. Some experimental probes for this possibility are suggested.     

A Note on Graph Pebbling

 We say that a graph G is Class 0 if its pebbling number is exactly equal to its number of vertices. For a positive integer d, let k(d) denote the least positive integer so that every graph G with diameter at most d and connectivity at least k(d) is Class 0. The existence of the function k was conjectured by Clarke, Hochberg and Hurlbert, who showed that if the function k exists, then it must satisfy k(d)=Ω(2 ^d /d). In this note, we show that k exists and satisfies k(d)=O(2 ^2d ). We also apply this result to improve the upper bound on the random graph threshold of the Class 0 property. Received: April 19, 1999 Final version received: February 15, 2000     

Generalizations of Graham’s pebbling conjecture

We investigate generalizations of pebbling numbers and of Graham’s pebbling conjecture that $\pi \left(G\square H\right)\le \pi \left(G\right)\pi \left(H\right)$, where $\pi \left(G\right)$ is the pebbling number of the graph $G$. We develop new machinery to attack the conjecture, which is now twenty years old. We show that certain conjectures imply others that initially appear stronger. We also find counterexamples that shows that Sjöstrand’s theorem on cover pebbling does not apply if we allow the cost of transferring a pebble from one vertex to an adjacent vertex to depend on the weight of the edge and we describe an alternate pebbling number for which Graham’s conjecture is demonstrably false.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

Pebbling in diameter two graphs and products of paths

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing those diameter two graphs of Class 0, extending results of Pachter, Snevily and Voxman. In fact we use this characterization to show that almost all graphs have Class 0. We also present a technical correction to Chung's alternate proof of a number theoretic result of Lemke and Kleitman via pebbling. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 119–128, 1997