On the contact dimensions of graphs

Every simple graphG=(V, E) can be represented by a family of equal nonoverlapping spheres {S _v :v V} in a Euclidean spaceR ⁿ in such a way thatuv E if and only ifS _u andS _v touch each other. The smallest dimensionn needed to representG in such a way is called the contact dimension ofG and it is denoted by cd(G). We prove that (1) cd(T)<(7.3) log |T| for every treeT, and (2)

Finite projective spaces and intersecting hypergraphs

Let ? be a family ofk-subsets on ann-setX andc be a real number 0 <c<1. Suppose that anyt members of ? have a common element (t ≧ 2) and every element ofX is contained in at mostc|?| members of ?. One of the results in this paper is (Theorem 2.9): If $$c = {{(q^{t - 1} + ... + q + 1)} \mathord{\left/ {\vphantom {{(q^{t - 1} + ... + q + 1)} {(q^t + ... + q + 1)}}} \right. \kern-\nulldelimiterspace} {(q^t + ... + q + 1)}}$$ . whereq is a prime power andn is sufficiently large, (n >n (k, c)) then The corresponding lower bound is given by the following construction. LetY be a (q ^t + ... +q + 1)-subset ofX andH ₁,H ₂, ...,H _|Y| the hyperplanes of thet-dimensional projective space of orderq onY. Let ? consist of thosek-subsets which intersectY in a hyperplane, i.e., ?={F∈( _k ^X ): there exists ani, 1≦i≦|Y|, such thatY∩F=H _i }.     

Density results for uniform families

A familyF of subsets is calledk-dense if there exists ak-element setA such that all 2 ^k of its subsets can be obtained in the formAF for someFF. Best possible bounds are obtained for the maximum number of sets in notk-densek-partite families. This is a consequence of a new rank formula for inclusion matrices.     

Atomic beam scattering from single crystal surfaces

Application of atom-scattering to a variety of surface problems is expanding rapidly, owing in large part to the extreme surface- sensitivity of this probe. Helium is particularly useful because of its low mass and chemical inertness. Beams with velocity spreads of less than one percent and wavelength of the order of one Angstrom can be formed by nozzle expansion.

The scattered flux from a clean, well-ordered crystal surface contains elastic and inelastic, coherent and incoherent, components. The coherent elastic component (i.e., the specular and diffracted beams) contains information about the crystallographic structure of the outer- most atomic layer of the crystal and about the interaction potential between the crystal and the scattered particle. The latter manifests itself in the form of resonances between the incoming free-particle state, and the two-dimensional Bloch states bound in the potential well at the surface. Elastic scattering theory has reached the point where the resonance signatures in the various diffracted beams can be predicted accurately.

Crystallographic information resides in the diffracted beam intensities. Theoretical interpretation is less well advanced, though some progress has been made with “hard-wall” models. Experimental studies of reconstructed surfaces and chemisorbed overlayers appear very promising.

In inelastic scattering, energy resolution has been achieved by both time-of-flight and diffraction methods. High-resolution studies on alkali halide surfaces have led to experimental determination of Rayleighwave dispersion relations over the full Brillouin zone. Preliminary results have also been obtained on some metals.     

Every large set of equidistant (0, +1, −1)-vectors forms a sunflower

A theorem of Deza asserts that ifH ₁, ...,H _m ares-sets any pair of which intersects in exactlyd elements and ifm ≧s ² −s+2, then theH _i form aΔ-system, i.e. . In other words, every large equidistant (0, 1)-code of constant weight is trivial. We give a (0, +1, −1) analogue of this theorem.     

Extremal k-edge-hamiltonian hypergraphs

An r-uniform hypergraph is k-edge-hamiltonian iff it still contains a hamiltonian-chain after deleting any k edges of the hypergraph. What is the minimum number of edges in such a hypergraph? We give lower and upper bounds for this question for several values of r and k.     

Ein Knotensatz mit Anwendung auf die Dimensionstheorie

Ohne Zusammenfassung     

Some best possible bounds concerning the traces of finite sets

LetX be ann-element set and ? a family of its subsets. Considering the setsF∩(X - {x}) for a given x ∈X, there might be some coincidences, namely, ifF and G differ only in x, then they have the same intersection withX - {x}. It is proved that if |?| ≤ 65n/14, then for an appropriatex ∈X, the number of coincidences is at most 9. Several similar, best possible bounds are obtained, continuing previous research by Bondy, Bollobás and the authors.