Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

The density of rational points on non-singular hypersurfaces

LetF(x) =F[x₁,…,x_n]∈ℤ[x₁,…,x_n] be a non-singular form of degree d≥2, and letN(F, X)=#{xεℤ ⁿ ;F(x)=0, |x|⩽X}, where . It was shown by Fujiwara [4] [Upper bounds for the number of lattice points on hypersurfaces,Number theory and combinatorics, Japan, 1984, (World Scientific Publishing Co., Singapore, 1985)] thatN(F, X)≪X ^n−2+2/n for any fixed formF. It is shown here that the exponent may be reduced ton - 2 + 2/(n + 1), forn ≥ 4, and ton - 3 + 15/(n + 5) forn ≥ 8 andd ≥ 3. It is conjectured that the exponentn - 2 + ε is admissable as soon asn ≥ 3. Thus the conjecture is established forn ≥ 10. The proof uses Deligne’s bounds for exponential sums and for the number of points on hypersurfaces over finite fields. However a composite modulus is used so that one can apply the ‘q-analogue’ of van der Corput’s AB process. Dedicated to the memory of Professor K G Ramanathan     

On Connected [g,f +1]-Factors in Graphs

Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G), and g and f two positive integral functions from V (G) to Z⁺-{1} such that g(v) ≤ f(v) ≤ d_G(v) for all v ∈V (G), where d_G(v) is the degree of the vertex v. It is shown that every graph G, including both a [g,f]-factor and a hamiltonian path, contains a connected [g,f +1]-factor. This result also extends Kano’s conjecture concerning the existence of connected [k,k+1]-factors in graphs. * The work of this author was supported by NSFC of China under Grant No. 10271065, No. 60373025. † The work of these authors was also supported in part by the US Department of Energy’s Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org) and by National Science Foundation (NSF/DBI-0354771,NSF/ITR-IIS-0407204).     

Computing the genus of the 2-amalgamations of graphs

The above authors [2] and S. Stahl [3] have shown that if a graphG is the 2-amalgamation of subgraphsG ₁ andG ₂ (namely ifG=G ₁∪G ₂ andG ₁∩G ₂={x, y}, two distinct points) then the orientable genus ofG,γ(G), is given byγ(G)=γ(G ₁)+γ(G ₂)+ε, whereε=0,1 or −1. In this paper we sharpen that result by giving a means by whichε may be computed exactly. This result is then used to give two irreducible graphs for each orientable surface.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

The intrinsic dimensionality of graphs

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ_∞ ^d , the infinite graph with vertex set ℤ ^d and an edge (u, v) whenever ∥u − v∥_∞ = 1. The growth rate of G, denoted ρ _G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ^ρ vertices. By simple volume arguments, dim(G) = Ω(ρ _G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ _G ) for every graph G. Previously, it was unknown whether dim(G) could be bounded above by any function of ρ _G . We show that a weaker form of Levin’s conjecture holds by proving that dim(G) = O(ρ _G log ρ _G ) for any graph G. We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) = Ω(ρ _G log ρ _G ). For several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ _G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. Supported by NSF grant CCR-0121555 and by an NSF Graduate Research Fellowship.     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

Uniformity over primes of tamely ramified splittings

We fix a prime p and let f(X) vary over all monic integer polynomials of fixed degree n. Given any possible shape of a tamely ramified splitting of p in an extension of degree n, we prove that there exists a rational function φ(X)∈ℚ(X) such that the density of the monic integer polynomials f(X) for which the splitting of p has the given shape in ℚ[X]/f(X) is φ(p) (here reducible polynomials can be neglected). As a corollary, we prove that, for p≥n, the density of irreducible monic polynomials of degree n in ℤ _p [X] is the value at p of a rational function φ _n (X)∈ℚ(X). All rational functions involved are effectively computable. Received: 15 September 1998 / Revised version: 21 October 1999     

On a graph packing conjecture by Bollobás,Eldridge and Catlin

Two graphs G ₁ and G ₂ of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets are disjoint. In 1978, Bollobás and Eldridge, and independently Catlin, conjectured that if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ n + 1, then G ₁ and G ₂ pack. Towards this conjecture, we show that for Δ(G ₁),Δ(G ₂) ≥ 300, if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ 0.6n + 1, then G ₁ and G ₂ pack. This is also an improvement, for large maximum degrees, over the classical result by Sauer and Spencer that G ₁ and G ₂ pack if Δ(G ₁)Δ(G ₂) < 0.5n. This work was supported in part by NSF grant DMS-0400498. The work of the second author was also partly supported by NSF grant DMS-0650784 and grant 05-01-00816 of the Russian Foundation for Basic Research. The work of the third author was supported in part by NSF grant DMS-0652306.     

Extremal clique coverings of complementary graphs

Letcc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graphG. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphsG onn vertices and Ḡ is the complement ofG inK _n . Several related open problems are also given.     

Privileged users in zero-error transmission over a noisy channel

The k-th power of a graph G is the graph whose vertex set is V(G) ^k , where two distinct k-tuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G), is lim _k→∞ α(G ^k )^1/k , where α(G) denotes the independence number of G. When G is the characteristic graph of a channel C, c(G) measures the effective alphabet size of C in a zero-error protocol. A sum of channels, C = Σ _i C _i , describes a setting when there are t ≥ 2 senders, each with his own channel C _i , and each letter in a word can be selected from any of the channels. This corresponds to a disjoint union of the characteristic graphs, G = Σ _i G _i . It is well known that c(G) ≥ Σ _i c(G _i ), and in [1] it is shown that in fact c(G) can be larger than any fixed power of the above sum. We extend the ideas of [1] and show that for every F, a family of subsets of [t], it is possible to assign a channel C _i to each sender i ∈ [t], such that the capacity of a group of senders X ⊂ [t] is high iff X contains some F ∈ F. This corresponds to a case where only privileged subsets of senders are allowed to transmit in a high rate. For instance, as an analogue to secret sharing, it is possible to ensure that whenever at least k senders combine their channels, they obtain a high capacity, however every group of k − 1 senders has a low capacity (and yet is not totally denied of service). In the process, we obtain an explicit Ramsey construction of an edge-coloring of the complete graph on n vertices by t colors, where every induced subgraph on exp vertices contains all t colors. Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research partially supported by a Charles Clore Foundation Fellowship.     

On A(X) → TC(X) for some X

Let X be a connected based space and p be a two-regular prime number. If the fundamental group of X has order p, we compute the two-primary homotopy groups of the homotopy fiber of the trace map A(X) → TC(X) relating algebraic K-theory of spaces to topological cyclic homology. The proof uses a theorem of Dundas and an explicit calculation of the cyclotomic trace map K(ℤ[C_p])→ TC(ℤ[C_p]).     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

Harmonic Functions on Homogeneous Spaces

 Given a locally compact group G acting on a locally compact space X and a probability measure σ on G, a real Borel function f on X is called σ-harmonic if it satisfies the convolution equation . We give conditions for the absence of nonconstant bounded harmonic functions. We show that, if G is a union of σ-admissible neighbourhoods of the identity, relative to X, then every bounded σ-harmonic function on X is constant. Consequently, for spread out σ, the bounded σ-harmonic functions are constant on each connected component of a [SIN]-group and, if G acts strictly transitively on a splittable metric space X, then the bounded σ-harmonic functions on X are constant which extends Furstenberg’s result for connected semisimple Lie groups. (Received 13 June 1998; in revised form 31 March 1999)     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

A characterization of the minimalbasis of the torus

D. König asks the interesting question in [7] whether there are facts corresponding to the theorem of Kuratowski which apply to closed orientable or non-orientable surfaces of any genus. Since then this problem has been solved only for the projective plane ([2], [3], [8]). In order to demonstrate that König’s question can be affirmed we shall first prove, that every minimal graph of the minimal basis of all graphs which cannot be embedded into the orientable surface f of genusp has orientable genusp+1 and non-orientable genusq with 1≦q≦2p+2. Then let f be the torus. We shall derive a characterization of all minimal graphs of the minimal basis with the nonorientable genusq=1 which are not embeddable into the torus. There will be two very important graphs signed withX ₈ andX ₇ later. Furthermore 19 graphsG ₁,G ₂, ...,G ₁₉ of the minimal basisM(torus, >₄) will be specified. We shall prove that five of them have non-orientable genusq=1, ten of them have non-orientable genusq=2 and four of them non-orientable genusq=3. Then we shall point out a method of determining graphs of the minimal basisM(torus, >₄) which are embeddable into the projective plane. Using the possibilities of embedding into the projective plane the results of [2] and [3] are necessary. This method will be called saturation method. Using the minimal basisM(projective plane, >₄) of [3] we shall at last develop a method of determining all graphs ofM(torus, >₄) which have non-orientable genusq≧2. Applying this method we shall succeed in characterizing all minimal graphs which are not embeddable into the torus. The importance of the saturation method will be shown by determining another graphG ₂₀≠G ₁,G ₂, ...,G ₁₉ ofM(torus, >₄).     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,x _k teX such thatx _i teE _j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday