Some Ramsey-Turán type results for hypergraphs

To everyk-graphG let(G) be the minimal real number such that for every>0 andn>n ₀(,G) everyk-graphH withn vertices and more than (+) ( ) edges contains a copy ofG. The real number (G) is defined in the same way adding the constraint that all independent sets of vertices inH have sizeo(n). Answering a problem of Erds and Sós it is shown that there exist infinitely manyk-graphs with 0<(G)<(G) for everyk3. It is worth noting that we were unable to find a singleG with the above property.This paper was written while the authors were visiting AT&T Bell Laboratories, Murray Hill, NJ 07974.     

The Colin de Verdière number and sphere representations of a graph

Colin de Vedière introduced an interesting linear algebraic invariant (G) of graphs. He proved that (G)2 if and only ifG is outerplanar, and (G)3 if and only ifG is planar. We prove that if the complement of a graphG onn nodes is outerplanar, then (G)n–4, and if it is planar, then (G)n–5. We give a full characterization of maximal planar graphs whose complementsG have (G)=n–5. In the opposite direction we show that ifG does not have twin nodes, then (G)n–3 implies that the complement ofG is outerplanar, and (G)n–4 implies that the complement ofG is planar.Our main tools are a geometric formulation of the invariant, and constructing representations of graphs by spheres, related to the classical result of Koebe about representing planar graphs by touching disks. In particular we show that such sphere representations characterize outerplanar and planar graphs.     

k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

Extending partial isomorphisms of graphs

Theorem Let X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a genericn-tuple of automorphism of the Rado graphR (the random countable graph): for almost all automorphism ₁,..., _n and ₁ ofR (in the sense of Baire category), (R,₁,..., _n ), (R,₁,..., _n ). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378.     

Packing directed circuits fractionally

LetG be a digraph, and letk1, such that no fractional packing of directed circuits ofG has value >k, when every vertex is given capacity 1. We prove there is a set ofO (k logk logk) vertices meeting all directed circuits ofG.     

First order properties of random posets

Let =(n,p) be a binary relation on the set [n]={1, 2, ..., n} such that (i,i) for every i and (i,j) with probability p, independently for each pair i,j [n], where i<j. Define as the transitive closure of and denote poset ([n], ) by R(n, p). We show that for any constant p probability of each first order property of R(n, p) converges as n .     

The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

On random minimum length spanning trees

We extend and strengthen the result that, in the complete graphK _n with independent random edge-lengths uniformly distributed on [0, 1], the expected length of the minimum spanning tree tends to(3) asn. In particular, ifK _n is replaced by the complete bipartite graphK _{n, n} then there is a corresponding limit of 2 (3).     

A strong approximation for logarithmic averages of partial sums of random variables

LetS _n be the partial sums of -mixing stationary random variables and letf(x) be a real function. In this note we give sufficient conditions under which the logarithmic average off(S _n / _n ) converges almost surely to _– f(x)d(x). We also obtain strong approximation forH(n)= _k=1 ⁿ k ^–1 f(S _k /k)=logn _– f(x)d(x) which will imply the asymptotic normality ofH(n)/log^1/2 n. But for partial sums of i.i.d. random variables our results will be proved under weaker moment condition than assumed for -mixing random variables.     

Upper bound for transversals of tripartite hypergraphs

We prove 2 7/9v for 3-partite hypergraphs. (This is an improvement of the trivial bound 3v.)     

Fine Analysis of the Quasi-Orderings on the Power Set

We pursue the fine analysis of the quasi-orderings and on the power set of a quasi-ordering (Q,). We set X Y if every xX is majorized in by some yY, and X Y if every yY is minorized in by some xX. We show that both these quasi-orderings are -wqo if and only if the original quasi-ordering is ( )-wqo. For this holds also restricted to finite subsets, thus providing an example of a finitary operation on quasi-orderings which does not preserve wqo but preserves bqo.     

Colouring a graph frugally

We prove that any graph with maximum degree sufficiently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log⁸ times in the neighbourhood of any vertex. We also show that for 1, the minimum number of colours required to colour any such graph so that each vertex appears at most times in the neighbourhood of any vertex is (+^1+1//), showing in particular that when =log/loglog, such a colouring cannot always be achieved with O() colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.The second two authors were supported by NATO Collaborative Research Grant #CRG950235.     

On the stochastic independence properties of hard-core distributions

A probability measurep on the set of matchings in a graph (or, more generally 2-bounded hypergraph) ishard-core if for some : [0,), the probabilityp(M) ofM is proportional to . We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, withM chosen according to the hard-core distributionp, MP () the matching polytope of , and >0, if the vector ofmarginals, (Pr(AM):A an edge of ), is in (1–) MP (), then the weights (A) are bounded by someA(). This eventually implies, for example, that under the same assumption, with fixed, as the distance betweenA, B tends to infinity.Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]–[13]).Supported in part by NSFThis work forms part of the author's doctoral dissertation [16]; see also [17]. The author gratefully acknowledges NSERC for partial support in the form of a 1967 Science and Engineering Scholarship.     

Brownian charges around loops

Summary Let (X _t ⁿ ) be a Poisson sequence of independent Brownian motions in ^d ,d3; Let be a compact oriented submanifold of d, of dimensiond–2 and volume ; let t be the sum of the windings of (X _s ⁿ , 0st) around ; then t/t converges in law towards a Cauchy variable of parameter /2. A similar result is valid when the winding is replaced by the integral of a harmonic 1-form in ^d .     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Covering the hypercube with a bounded number of disjoint snakes

We present a construction of an induced cycle in then-dimensional hypercubeI[n] (n2), and a subgroup _n ofI[n] considered as the group ₂ ⁿ , such that | _n |16 and the induced cycle uses exactly one element of every coset of _n . This proves that for anyn2 the vertices ofI[n] can be covered using at most 16 vertex-disjoint induced cycles.     

Almost Covers Of 2-Arc Transitive Graphs

Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case K _v+1 is covered by results of Gardiner and Praeger. We consider here the general case where K _v+1, and prove that, for some even integer n 4, is a near n-gonal graph with respect to a certain G-orbit on n-cycles of . Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .)     

On the singular graph and the Weyr characteristic of anM-matrix

LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA _ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA _i, A_ij, , A_l.Let ₁ be the set of maximal elements ofS, and define thep-th level _p ,p = 2, 3, , inductively as the set of maximal elements ofS \( _{1 p-1}). Denote by _p the number of elements in _p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( ₁, ₂,, _h ), where ₁ + + _p = dim KerA ^p ,p = 1, 2, , and _h > 0, _h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( ₁, , _h) if and only if certain submatricesD _p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( ₁, , _h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.     

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.     

Circular Chromatic Number and Mycielski Graphs

As a natural generalization of graph coloring, Vince introduced the star chromatic number of a graph G and denoted it by ^*(G). Later, Zhu called it circular chromatic number and denoted it by _c(G). Let (G) be the chromatic number of G. In this paper, it is shown that if the complement of G is non-hamiltonian, then _c(G)=(G). Denote by M(G) the Mycielski graph of G. Recursively define M^m(G)=M(M^m–1(G)). It was conjectured that if mn–2, then _c(M^m(K_n))=(M^m(K_n)). Suppose that G is a graph on n vertices. We prove that if , then _c(M(G))=(M(G)). Let S be the set of vertices of degree n–1 in G. It is proved that if |S| 3, then _c(M(G))=(M(G)), and if |S| 5, then _c(M²(G))=(M²(G)), which implies the known results of Chang, Huang, and Zhu that if n3, _c(M(K_n))=(M(K_n)), and if n5, then _c(M²(K_n))=(M²(K_n)).* Research supported by Grants from National Science Foundation of China and Chinese Academy of Sciences.