K 1,p k-factorization of complete bipartite graphs

Abstract. In this paper, it is shown that a sufficient condition for the existence of a     

Intersection theorems with geometric consequences

In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ₀, μ₁, ..., μ_s are distinct residues modp (p is a prime) such thatk ≡ μ₀ (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μ_i (modp) for somei, 1 ≦i≦s, then |ℱ|≦( _s ⁿ ). As a consequence we show that ifR ⁿ is covered bym sets withm<(1+o(1)) (1.2) ⁿ then there is one set within which all the distances are realised. It is left open whether the same conclusion holds for compositep.     

Sharp concentration of the chromatic number on random graphsG n,p

The distribution of the chromatic number on random graphsG _{n, p} is quite sharply concentrated. For fixedp it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degreepn is less thann ^1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.     

Clean triangulations

A polyhedron on a surface is called a clean triangulation if each face is a triangle and each triangle is a face. LetS _p (resp.N _p ) be the closed orientable (resp. nonorlentable) surface of genusp. If (S) is the smallest possible number of triangles in a clean triangulation ofS, the results are: (N ₁)=20, (S ₁)=24, lim(S _p )p ^–1=4, lim(N _p )p ^–1=2 forp.     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Some graphs with small second eigenvalue

For any prime,p, we construct a Cayley graph on the group,G, of affine linear transformations ofℤ/pℤ of degree 2(p−1) and second eigenvalue with the following special property: the adjacency matrix of the graph is supported on the “blocks” associated to the trivial representation and the irreducible representation of sizep−1. SinceG is of orderp(p−1), the correspondingt-uniform Cayley hypergraph has essentially optimal second eigenvalue for this degree and size of the graph (see [2] for definitions). En route we give, for any integerk>1, a simple Cayley graph onp ^k nodes of degreep of second eigenvalue . The author wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8858788, and the Office of Naval Research under Grant N00014-87-K-0467.     

Complete Minors In <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">s,s</Emphasis></Subscript>-Free Graphs

We prove that for a fixed integer s2 every K _s,s -free graph of average degree at least r contains a K _p minor where . A well-known conjecture on the existence of dense K _s,s -free graphs would imply that the value of the exponent is best possible. Our result implies Hadwigers conjecture for K _s,s -free graphs whose chromatic number is sufficiently large compared with s.     

Clique coverings of the edges of a random graph

The edges of the random graph (with the edge probabilityp=1/2) can be covered usingO(n ²lnlnn/(lnn)²) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1–)n ²/(2lgn)².Research supported in part by ONR Grant N00014-85K0570 and by NSA/MSP Grant MDA904-90-H-4011.     

Crystallographic reptiles

We consider tilings ofR ⁿ by copies of a compact setA under the action of a crystallographic group, such that the union ofk suitably chosen tiles is affinely isomorphic toA. For dimensionn=2 we show that for eachk2 there is a finite number of isomorphy classes of such setsA which are homeomorphic to a disk. We give an algorithm which determines all disk-like tiles for a given group and numberk. The algorithm will be applied to the groupsp2 andp3 withk=3.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

We study random subgraphs of the n-cube {0,1}ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p−p_c(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2^−n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log 2)nε⁻², and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for the size of the largest component is at least Θ(ε2ⁿ), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,” and relies heavily on the specific geometry of the n-cube.     

The Minimum Area of Convex Lattice <Emphasis Type="Italic">n</Emphasis>-Gons

Let A(n) be the minimum area of convex lattice n-gons. We prove that lim A(n)/n³ exists. Our computations suggest that the value of the limit is very close to 0.0185067....* Partially supported by Hungarian National Science Foundation Grants T 032452 and T 029255.     

OnK 4-free subgraphs of random graphs

For 0<1 and graphsG andH, writeGH if any -proportion of the edges ofG spans at least one copy ofH inG. As customary, writeK ^r for the complete graph onr vertices. We show that for every fixed real >0 there exists a constantC=C() such that almost every random graphG _n,p withp=p(n)Cn ^–2/5 satisfiesG _{n,p 2/3+} K ⁴. The proof makes use of a variant of Szemerédi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerningH-free subgraphs of random graphs in the spirit of the Erds-Stone theorem are discussed.The first author was partially supported by FAPESP (Proc. 93/0603-1) and by CNPq (Proc. 300334/93-1 and ProTeM-CC-II Project ProComb). Part of this work was done while the second author was visiting the University of São Paulo, supported by FAPESP (Proc. 94/4276-8). The third author was partially supported by the NSF grant DMS-9401559.     

Rédei-Funktionen für Zweierpotenzen

L. Rédei has introduced in 1946 a class of rational functions over finite fields of orderp ^t –p being an odd prime — and has proved some interesting results on permutations which are induced by these functions. Recently, similar results have been found for factor rings of the integers of orderp ^t ; moreover, these functions have been applied to construct public key cryptosystems. In this paper we consider functions of Rédei type over finite fields and factor rings of the integers of order 2 ^t . We show that most of the results for oddp also hold in this case.

     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

SPACELIKE SUBMANIFOLDS IN THE DE SITTER SPACE Sp^（n＋p）（c）WITH CONSTANT SCALAR CURVATURE

Let M^n be a closed spacelike submanifold isometrically immersed in de Sitter space Sp^(n p)(c)， Denote by R,H and S the normalized scalar curvature,the mean curvature and the square of the length of the second fundamental form of M^n ,respectively. Suppose R is constant and R≤c. The pinching problem on S is studied and a rigidity theorem for M^n immersed in Sp^(n p)(c) with parallel normalized mean curvature vector field is proved. When n≥3, the pinching constant is the best. Thus, the mistake of the paper “Space-like hypersurfaces in de Sitter space with constant scalar curvature”(see Manus Math, 1998,95 :499-505) is corrected. Moreover,the reduction of the codimension when M^n is a complete submanifold in Sp^(n p)(c) with parallel normalized mean curvature vector field is investigated.     

CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHSWITH 5n VERTICES

For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained.     

On tree‐decompositions of one‐ended graphs

A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays.     

A compatible‐incompatible decomposition of symmetric tensors in Lp with application to elasticity

In this paper, we prove the Saint‐Venant compatibility conditions in L^p for p∈(1,+∞), in a simply connected domain of any space dimension. As a consequence, alternative, simple, and direct proofs of some classical Korn inequalities in L^p are provided. We also use the Helmholtz decomposition in L^p to show that every symmetric tensor in a smooth domain can be decomposed in a compatible part, which is the symmetric part of a displacement gradient, and in an incompatible part, which is the incompatibility of a certain divergence‐free tensor. Moreover, under a suitable Dirichlet boundary condition, this Beltrami‐type decomposition is proved to be unique. This decomposition result has several applications, one of which being in dislocation models, where the incompatibility part is related to the dislocation density and where 1 < p < 2. This justifies the need to generalize and prove these rather classical results in the Hilbertian case (p = 2), to the full range p∈(1,+∞). Copyright © 2015 John Wiley & Sons, Ltd.