The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

Isometric dilations in nest algebras

LetT be a contraction acting in a separable Hilbert space and leaving invariant a nest of subspaces of . We answer the question: when doesT have an isometric extension to which leaves invariant the nest = {N N :N ;}.     

On sequences of Dirichlet polynomials uniformly bounded on half planes

Given and a sequence of Dirichlet polynomials estimates for the coefficientsa _n are proved if {_n} is uniformly bounded on a region containing a half plane. Thereby a result is obtained which is an analogue of a known result for polynomials, that is for theA-transforms of the geometric sequence; moreover a Jentzsch type theorem for {_n(z)} is derived.     

Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs

We prove that every Eulerian orientation of K_m,n contains arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004     

For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

Berger-Shaw's theorem forp-hyponormal operators

For an-multicyclicp-hyponormal operatorT, we shall show that |T|^2p –|T ^*|^2p belongs to the Schatten and that tr Area ((T)).     

Asymptotic solution for a new class of forbiddenr-graphs

We consider the problem of finding ex (n; G), defined as the maximal number of edges anr-graph onn vertices can have that contains no subgraph isomorphic toG. We construct certainr-graphsG for which we find the coefficient(G) of the asymptotic expansion ex(n;G)== asn.     

Convex Embeddings and Bisections of 3-Connected Graphs1

Given two disjoint subsets T ₁ and T ₂ of nodes in an undirected 3-connected graph G = (V, E) with node set V and arc set E, where and are even numbers, we show that V can be partitioned into two sets V ₁ and V ₂ such that the graphs induced by V ₁ and V ₂ are both connected and holds for each j = 1,2. Such a partition can be found in time. Our proof relies on geometric arguments. We define a new type of convex embedding of k-connected graphs into real space R ^k-1 and prove that for k = 3 such an embedding always exists. ¹ A preliminary version of this paper with title Bisecting Two Subsets in 3-Connected Graphs appeared in the Proceedings of the 10th Annual International Symposium on Algorithms and Computation, ISAAC 99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741, 425&ndash;434, 1999.     

Unit-distance graphs,graphs on the integer lattice and a Ramsey type result

Summary Let (R ², 1) denote the graph withR ² as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R ², 1) is still open; however,(R ², 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R ², 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z ²,r, ) denote a graph with vertex setZ ² and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r – ,r + ]. A simple graph is faithfully -recurring inZ ² if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z ²,r, ) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R ², 1) if and only ifG is faithfully -recurring inZ ². In this paper we prove that(Z ²,r, ) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ ² either there exists a monochromatic pair of vertices with their distance in the closed interval [r – ,r + ] or there exists a set of three vertices closest to each other with three distinct colors.     

Universal coverings of PL-manifolds via coloured graphs

Summary By means of techniques and results concerning maps on surfaces [JS] and edge-coloured graphs representing PL-manifolds [FGG], we prove the existence of an infinite ball complexP(n), n > 1, such thatevery orientable PL-manifold of dimension n is a quotient of |P(n)| by the action of a finite index subgroup of a Fuchsian group with signature ,with h(2) = h(3) = 4 and h(n) = 2, for n > 3. The core of the proof is that all orientable PL-manifolds of dimensionn can be represented by edge-coloured graphs which are quotients of a universal graph, only depending onn.     

Randomized graph products, chromatic numbers, and the Lovász ϑ-function

For a graphG, let (G) denote the size of the largest independent set inG, and let (G) denote the Lovász -function onG. We prove that for somec>0, there exists an infinite family of graphs such that \alpha (G)n/2^{c\sqrt {\log n} }$$ " align="middle" border="0"> , wheren denotes the number of vertices in a graph. this disproves a known conjecture regarding the function.As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph products. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.Incumbent of the Joseph and Celia Reskin Career Development Chair. Yigal Alon Fellow     

Cycles through specified vertices

Recently, various authors have obtained results about the existence of long cycles in graphs with a given minimum degreed. We extend these results to the case where only some of the vertices are known to have degree at leastd, and we want to find a cycle through as many of these vertices as possible. IfG is a graph onn vertices andW is a set ofw vertices of degree at leastd, we prove that there is a cycle through at least vertices ofW. We also find the extremal graphs for this property.Research supported in part by NSF Grant DMS 8806097     

Set Systems with few Disjoint Pairs

Let X = {1, . . . , n}, and let be a family of subsets of X. Given the size of , at least how many pairs of elements of must be disjoint? In this paper we give a lower bound for the number of disjoint pairs in . The bound we obtain is essentially best possible. In particular, we give a new proof of a result of Frankl and of Ahlswede, that if satisfies then contains at least as many disjoint pairs as X^(r).The situation is rather different if we restrict our attention to : then we are asking for the minimum number of edges spanned by a subset of the Kneser graph of given size. We make a conjecture on this lower bound, and disprove a related conjecture of Poljak and Tuza on the largest bipartite subgraph of the Kneser graph.* Research partially supported by NSF grant DMS-9971788     

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.     

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.     

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Ohba has conjectured [7] that if G has 2 (G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 (G)+1 by * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.     

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.     

Weakly union-free maximum packings

Frankl and Füredi [11] established that the largest number of 3-subsets of ann-set, for which no four distinct setsA,B,D satisfyAB=CD, is at most . Chee, Colbourn, and Ling [6] established that this upper bound is met with few exceptions whenn0, 1 (mod 3). In this paper, it is established that the upper bound is also met with few exceptions whenn2 (mod 3).The research was supported in part by the US Army Research Office under Grant DAAG55-98-1-0272.     

Panconnected graphs II

A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that d_G(u, v)lp – 1, whered _G (u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected.