The Moore Bound for Irregular Graphs

 What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover irregular graphs as well, yielding an affirmative answer to an old open problem ([4] p. 163, problem 10). Received: June 27, 2000 Final version received: July 3, 2001     

A Ramsey‐type result for the hypercube

We prove that for every fixed k and ? ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Q_n with k colors contains a monochromatic cycle of length 2 ?. This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which are Ramsey, that is, have the property that for every k, any k‐edge coloring of a sufficiently large Q_n contains a monochromatic copy of H. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 196–208, 2006     

On the evolution of islands

Letn cells be arranged in a ring, or alternatively, in a row. Initially, all cells are unmarked. Sequentially, one of the unmarked cells is chosen at random and marked until, aftern steps, each cell is marked. After thekth cell has been marked the configuration of marked cells defines some number of islands: maximal sets of adjacent marked cells. Let ξ _k denote the random number of islands afterk cells have been marked. We give explicit expressions for moments of products of ξ _k ’s and for moments of products of 1/ξ _k ’s. These are used in a companion paper to prove that if a random graph on the natural number is made by drawing an edge betweeni≧1 andj>i with probabilityλ/j, then the graph is almost surely connected ifλ>1/4 and almost surely disconnected ifλ≦1/4.     

Separation of charge and spin degrees of freedom in the Hubbard model

The representation of the electron field operators separating charge from spin and providing transmutations between spin and isospin quantum numbers has been derived for any dimension. In this representation the interaction term in the Hubbard model is expressed in a bilinear form of quasiparticle field operators. The quasiparticles are spinless fermions with the electron electric charge. The consequence of this representation is that superconductivity in the strong coupling Hubbard model is due to odd wave pairings of electrons.The author expresses his sincere gratitude to Professor S. Stenholm for discussions and for the warm hospitality at the Research Institute for Theoretical Physics, University of Helsinki where this work has began. He would especially like to thank Professor C. Cronström who played an important role in the early and final stages of this work. Professor Anderson is acknowledged for providing the author with two chapters of his book (not yet published) quoted in the Discussion.     

Simple Constructions of Almost k-wise Independent Random Variables

We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o(1)) (log log n + k/2 + log k + log 1/?), where ? is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ? < 1/(k log n)). An additional advantage of our constructions is their simplicity.     

Sub-Ramsey numbers for arithmetic progressions

Letm 3 andk 1 be two given integers. Asub-k-coloring of [n] = {1, 2,...,n} is an assignment of colors to the numbers of [n] in which each color is used at mostk times. Call an arainbow set if no two of its elements have the same color. Thesub-k-Ramsey number sr(m, k) is defined as the minimumn such that every sub-k-coloring of [n] contains a rainbow arithmetic progression ofm terms. We prove that((k – 1)m ²/logmk) sr(m, k) O((k – 1)m ² logmk) asm , and apply the same method to improve a previously known upper bound for a problem concerning mappings from [n] to [n] without fixed points.Research supported in part by Allon Fellowship and by a Bat Sheva de-Rothschild grant.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences, grant No. 1-3-86-264.     

Every 8-uniform 8-regular hypergraph is 2-colorable

As is well known, Lovász Local Lemma implies that everyd-uniformd-regular hypergraph is 2-colorable, providedd 9. We present a different proof of a slightly stronger result; everyd-uniformd-regular hypergraph is 2-colorable, providedd 8.Research supported in part by Allon Fellowship and by a grant from the United States Israel Binational Science Foundation.     

On sums of subsets of a set of integers

Forr2 letp(n, r) denote the maximum cardinality of a subsetA ofN={1, 2,...,n} such that there are noBA and an integery with b=y ^r. It is shown that for any>0 andn>n(), (1+o(1))2^1/(r+1) n ^{(r–1)/(r+1)}p(n, r)n ^+2/3 for allr5, and that for every fixedr6,p(n, r)=(1+o(1))·2^1/(r+1) n ^{(r–1)/(r+1)} asn. Letf(n, m) denote the maximum cardinality of a subsetA ofN such that there is noBA the sum of whose elements ism. It is proved that for 3n ^6/3+mn ²/20 log² n andn>n(), f(n, m)=[n/s]+s–2, wheres is the smallest integer that does not dividem. A special case of this result establishes a conjecture of Erds and Graham.Research supported in part by Allon Fellowship, by a Bat-Sheva de Rothschild Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Superconductivity in crystals with covalent bonds

Novel types of ground states associated with properties of heavy fermion systems are derived for crystals with covalent bonds generated by short-range exchange forces between valence electrons of atoms localized at lattice sites. It is shown that the short-range exchange forces can give rise to a narrow energy band in which electrons can exhibit an enormous effective mass. The same exchange forces provide the microscopic mechanism for spin-singlet pairing of electrons into Cooper pairs which are responsible for superconductivity in these systems. This superconductivity exhibits several different anisotropic superconducting states. The effective mass, Fermi energy, specific heat, Pauli susceptibility, critical temperatures and critical magnetic field of heavy fermion systems are calculated and compared with experimental data.The authors thank Dr. . Jano for discussions.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.