Generating and counting triangular systems

Lunnon has defined a triangularp-mino as an edge-connected configuration ofp cells from the triangle plane grid with vertices of degree 6. A triangular system is a triangularp-mino without any holes. On the other hand we can say that a triangular system is a part of a triangular grid with vertices of degree 6, consisting of all edges and vertices of some closed broken lineC without intersections (a circuit in the triangle grid), and all edges and vertices in the interior ofC. It is obvious that any closed broken lineC without intersections uniquely determines a triangular system. In this paper a method of generating triangular systems is presented.     

On Bateman's method for second kind integral equations

Summary Under suitable conditions, we prove the convergence of the Bateman method for integral equations defined over bounded domains inR ^d ,d1. The proof makes use of Hilbert space methods, and requires the integral operator to be non-negative definite. For one-dimensional integral equations over finite intervals, estimated rates of convergence are obtained which depend on the smoothness of the kernel, but are independent of the inhomogeneous term. In particular, for aC kernel andn reasonably spaced Bateman points, the convergence is shown to be faster than any power of 1/n. Numerical calculations support this result.     

A new upper bound for the length of snakes

Ad-dimensional circuit code of spreads is a simple circuitC in the graph of thed-dimen sional unit cube with the property that for any verticesx andy ofC which differ in exactlyr co-ordinates,r<s, there exists a path fromx toy consisting ofr edges ofC. This property is useful for detecting and limiting errors. In this paper we give a new upper bound for the maximum length of ad-dimensional circuit code of spread 2.     

Two-sided estimates on singular values for a class of integral operators on the semi-axis

(Quasi)-norms inC _p andC _{p, w} of weighted operators of the integration of (fractional) order are estimated. It is shown that, in most cases, the estimates obtained are sharp both in order and in function classes for the weight function involved.     

On the cube problem of Las Vergnas

We prove a conjecture of Las Vergnas in dimensions d7: The matroid of the d-dimensional cube C ^d has a unique reorientation class. This extends a result of Las Vergnas, Roudneff and Salaün in dimension 4. Moreover, we determine the automorphism group G ^d of the matroid of the d-cube C ^d for arbitrary dimension d, and we discuss its relation to the Coxeter group of C ^d . We introduce matroid facets of the matroid of the d-cube in order to evaluate the order of G ^d . These matroid facets turn out to be arbitrary pairs of parallel subfacets of the cube. We show that the Euclidean automorphism group W ^d is a proper subgroup of the group G ^d of all matroid symmetries of the d-cube by describing genuine matroid symmetries for each Euclidean facet. A main theorem asserts that any one of these matroid symmetries together with the Euclidean Coxeter symmetries generate the full automorphism group G ^d . For the proof of Las Vergnas' conjecture we use essentially these symmetry results together with the fact that the reorientation class of an oriented matroid is determined by the labeled lower rank contractions of the oriented matroid. We also describe the Folkman-Lawrence representation of the vertex figure of the d-cube and a contraction of it. Finally, we apply our method of proof to show a result of Las Vergnas, Roudneff, and Salaün that the matroid of the 24-cell has a unique reorientation class, too.     

A criterion for the affine equivalence of cell complexes inR d and convex polyhedra inR d+1

A criterion is given that decides, for a convex tilingC ofR ^d , whetherC is the projection of the faces in the boundary of some convex polyhedronP inR ^d+1. Its applicability is restricted neither by the properties nor by the dimension ofC. It turns out to be conceptually simpler than other criteria and allows the easy examination of various classes of cell complexes. In addition, the criterion is constructive, that is, it can be used to constructP provided it exists.Research was supported by the Austrian Fonds zur Foerderung der wissenschaftlichen Forschung.     

Weakly singular integral equations with operator-valued kernels and an application to radiation transfer problems

The standard problem of radiation transfer in a bounded regionG ⁿ can be reformulated as a weakly singular integral equation with an unknown functionu: GC(S ^n–1) and a kernelK: ((G × G }x=y}, which is continuously differentiable with respect to the operator strong convergence topology. We take these observations into the basis of an abstract treatment of weakly singular integral equations with (E)-valued kernels, whereE is a Banach space. Our purpose is to characterize the smoothness of the solution by proving that it belongs to special weighted spaces of smooth functions. On the way, realizing the proof techniques, we establish the compactness of the integral operator or its square inL _p (G,E),BC(G,E), and other spaces of interest in numerical analysis as well as in weighted spaces of smooth functions. The smoothness results are specified for the standard problem of radiation transfer as well as for the corresponding eigenvalue problem.     

D-Dimensional hypercubes and the Euler and MacNeish conjectures

We give a construction for large sets of mutually orthogonal hypercubes of dimensionald given sets of mutually orthogonal latin squares and hypercubes of lower dimension. We also considerd>-2 dimensional versions of the Euler and MacNeish conjectures as well as discussing applications to improved constructions of (t, m, s)-nets, useful in pseudorandom number generation and quasi-Monte-Carlo methods of numerical integration.This author would like to thank the National Security Agency for partial support under grant agreement # MDA 904-92-H-3044.     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.     

Extended Keller graph and its properties

Abstract

In the paper extended Keller graph is defined and some of its properties, such as Hamiltonian, the independence number, the chromatic number, etc., are proved. Moreover, the size of a maximum clique of for d = 2, 3, 4 and d ≥ 8 is given and for d = 5, 6, 7 a conjecture is stated.     

An upper bound for the cardinality of ans-distance subset in real euclidean space,II

It is shown that ifX is ans-distance subset inR ^d , then |X|≦( _s ^d+s ). Supported in part by NSF grant MCS7903128 A01. Supported in part by NSF grant MCS.     

Inverse closedness ofC *-algebras in Banach algebras

LetA denote a unital Banach algebra, and letB denote aC ^*-algebra which is contained as a unital subalgebra inA. We prove thatB is inverse closed inA if the norms ofA andB coincide. This generalizes well known result about inverse closedness ofC ^*-subalgebras inC ^*-algebras.     

Extremal properties of some geometric processes

In this paper some isoperimetric inequalities for stationary random tessellations are discussed. At first, classical results on deterministic tessellations in the Euclidean plane are extended to the case of random tessellations. An isoperimetric inequality for the random Poisson polygon is derived as a consequence of a theorem of Davidson concerning an extremal property of tessellations generated by random lines inR ². We mention extremal properties of stationary hyperplane tessellations inR ^d related to Davidson's result in cased=2. Finally, similar problems for random arrangements ofr-flats inR ^d are considered (r).This work was done while the author was visiting the University of Strathclyde in Glasgow.     

A perturbation theorem for positive contraction semigroups on L 1-spaces with applications to transport equations and Kolmogorov's differential equations

In this paper, a criterion is given for assuring that a linear positive contraction C ₀-semigroup defined on an L ¹-space is generated by the closure of A+B, A and B being suitable unbounded linear operators. Furthermore, this criterion is applied to the transport equation, Kolmogorov's differential equations, and a transport equation modelling cell growth.     

THE EIGENVALUE DISTRIBUTION OF A HUBERT-SCHMIDT-TYPE OPERATOR

Abstract

We prove the following theorem in answer to a question raised by P Nowosad and R Tovar in [3]. If K is a kernel operator on L²(x,u) with kernel K(x, y) if P(x): = U_X |K(x, y)|² d μ(y))½ and Q(x): = (U_X |K (y, x)|² d μ(y))½ and if _x PQdμ < ∞, then σ|λ_i|² < ∫_X PQd μ where (λ_i) is the se = zuence of eigenvalues of K.     

Sur le comportement asymptotique des potentiels d'une chaîne de Markov sur ℝ d

Résumé Dans cet article j'étudie le comportement à l'infini des potentiels des chaînes de Markov sur ^d (d3) proches du mouvement brownien, tout spécialement le cas des marches aléatoires, ainsi que des critères de transience et de récurrence inspirés de la méthode utilisée.

---

We study the asymptotic behaviour of potentials of Markov chains on ^d (d3), closed to Brownian motion, and particularly the case of random walks. Following a similar approach, we give transience and recurrence criteria.

     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

An upper bound for the cardinality of ans-distance subset in real euclidean space

IfX is ans-distance subset inR ^d , then |X|<( _s ^d+s )+( _s-1 ^d+s-1 . Supported in part by NSF grant MCS—7903128 (OSURF 711977).     

A generalization of group difference sets and the matrix equationA m =dI+λJ

LetG be a finite group. In this paper, we will study the-group matrices forG which satisfy the matrixA ^m =dI+J and we will show that the existence of such a solution is equivalent to the existence of a combinatorial structure inG which is a generalization of group difference sets.     

On eigenvalues of differentiable positive definite kernels

If a positive definite kernelK(x, y) has thepth order partial derivative ( ^p /y ^p )K(x,y) continuous on the square [0,1]², we show that the eigenvalues of the integral operator generated byK(x, y) are asymptoticallyo(1/n ^p+1 ). We also obtain the anticipated asymptotic estimate when ( ^p /y ^p )K(x,y) satisfies further a Lipschitz condition iny of order 0<1. These results, which extend some classical estimates of I. Fredholm and H. Weyl under the additional positive definiteness assumption, are based on two interesting inequalities of K. Fan.