Kruskal-Katona type theorems for clique complexes arising from chordal and strongly chordal graphs

A forest is the clique complex of a strongly chordal graph and a quasi-forest is the clique complex of a chordal graph. Kruskal-Katona type theorems for forests, quasi-forests, pure forests and pure quasi-forests will be presented.     

Coloring number and on-line Ramsey theory for graphs and hypergraphs

Let c,s,t be positive integers. The (c,s,t)-Ramsey game is played by Builder and Painter. Play begins with an s-uniform hypergraph G ₀=(V,E ₀), where E ₀=Ø and V is determined by Builder. On the ith round Builder constructs a new edge e _i (distinct from previous edges) and sets G _i =(V,E _i ), where E _i =E _i?1∪{e _i }. Painter responds by coloring e _i with one of c colors. Builder wins if Painter eventually creates a monochromatic copy of K _s ^t , the complete s-uniform hypergraph on t vertices; otherwise Painter wins when she has colored all possible edges.We extend the definition of coloring number to hypergraphs so that χ(G)≤col(G) for any hypergraph G and then show that Builder can win (c,s,t)-Ramsey game while building a hypergraph with coloring number at most col(K _s ^t ). An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser. The (p,s,t)-survival game begins with an s-uniform hypergraph H ₀ = (V,Ø) with an arbitrary finite number of vertices and no edges. Let H _i?1=(V _i?1,E _i?1) be the hypergraph constructed in the first i ? 1 rounds. On the i-th round Presenter plays by presenting a p-subset P _i ?V _i?1 and Chooser responds by choosing an s-subset X _i ?P _i . The vertices in P _i ? X _i are discarded and the edge X _i added to E _i?1 to form E _i . Presenter wins the survival game if H _i contains a copy of K _s ^t for some i. We show that for positive integers p,s,t with s≤p, Presenter has a winning strategy.     

Note on limits of finite graphs

We prove that for any weakly convergent sequence of finite graphs with bounded vertex degrees, there exists a topological limit graphing.     

Independent systems of representatives in weighted graphs

The following conjecture may have never been explicitly stated, but seems to have been floating around: if the vertex set of a graph with maximal degree Δ is partitioned into sets V _i of size 2Δ, then there exists a coloring of the graph by 2Δ colors, where each color class meets each V _i at precisely one vertex. We shall name it the strong 2Δ-colorability conjecture. We prove a fractional version of this conjecture. For this purpose, we prove a weighted generalization of a theorem of Haxell, on independent systems of representatives (ISR’s). En route, we give a survey of some recent developments in the theory of ISR’s. The research of the first author was supported by grant no 780/04 from the Israel Science Foundation, and grants from the M. & M. L. Bank Mathematics Research Fund and the fund for the promotion of research at the Technion. The research of the third author was supported by the Sacta-Rashi Foundation.     

Connected but not path-connected subspaces of infinite graphs

Solving a problem of Diestel [9] relevant to the theory of cycle spaces of infinite graphs, we show that the Freudenthal compactification of a locally finite graph can have connected subsets that are not path-connected. However we prove that connectedness and path-connectedness to coincide for all but a few sets, which have a complicated structure.     

Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

Arc-disjoint in-trees in directed graphs

Given a directed graph D = (V,A) with a set of d specified vertices S = {s ₁,…, s _d } ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ _i=1 ^d f(s _i ) arc-disjoint in-trees denoted by T _i,1,T _i,2,…, for every i = 1,…,d such that T _i,1,…, are rooted at s _i and each T _i,j spans the vertices from which s _i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case. Supported by JSPS Research Fellowships for Young Scientists. Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan.     

Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

Colored graphs without colorful cycles

A colored graph is a complete graph in which a color has been assigned to each edge, and a colorful cycle is a cycle in which each edge has a different color. We first show that a colored graph lacks colorful cycles iff it is Gallai, i.e., lacks colorful triangles. We then show that, under the operation mon ≡ m + n − 2, the omitted lengths of colorful cycles in a colored graph form a monoid isomorphic to a submonoid of the natural numbers which contains all integers past some point. We prove that several but not all such monoids are realized. We then characterize exact Gallai graphs, i.e., graphs in which every triangle has edges of exactly two colors. We show that these are precisely the graphs which can be iteratively built up from three simple colored graphs, having 2, 4, and 5 vertices, respectively. We then characterize in two different ways the monochromes, i.e., the connected components of maximal monochromatic subgraphs, of exact Gallai graphs. The first characterization is in terms of their reduced form, a notion which hinges on the important idea of a full homomorphism. The second characterization is by means of a homomorphism duality. The first author would like to express his thanks for support by project LN 00A056 of the Ministry of Education of the Czech Republic. The second author would like to express his thanks for support by project LN 00A056 of the Ministry of Education of the Czech Republic, by the NSERC of Canada and by the Gudder Trust of the University of Denver.     

Coloring even-faced graphs in the torus and the Klein bottle

We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C(Z ₁₃; 1,5). We also prove that a non-bipartite quadrangulation of the Klein bottle is 3-colorable if and only if it has no non-contractible separating cycle of length at most four and no odd walk homotopic to a non-contractible two-sided simple closed curve. These results settle a conjecture of Thomassen and two conjectures of Archdeacon, Hutchinson, Nakamoto, Negami and Ota. Institute for Theoretical Computer Science is supported as project 1M0545 by the Ministry of Education of the Czech Republic. The author was visiting Georgia Institute of Technology as a Fulbright scholar in the academic year 2005/06. Partially supported by NSF Grants No. DMS-0200595 and DMS-0354742.     

On end degrees and infinite cycles in locally finite graphs

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.     

On embeddability and stresses of graphs

Gluck has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that already the K ₅-minor freeness guarantees the stress freeness. More generally, we prove that every K _r+2-minor free graph is generically r-stress free for 1≤r≤4. (This assertion is false for r≥6.) Some further extensions are discussed. Supported by an I.S.F. grant.     

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.     

On the measure of intersecting families,uniqueness and stability

Let t≥1 be an integer and let A be a family of subsets of {1,2,…,n} every two of which intersect in at least t elements. Identifying the sets with their characteristic vectors in {0,1} ⁿ we study the maximal measure of such a family under a non uniform product measure. We prove, for a certain range of parameters, that the t-intersecting families of maximal measure are the families of all sets containing t fixed elements, and that the extremal examples are not only unique, but also stable: any t-intersecting family that is close to attaining the maximal measure must in fact be close in structure to a genuine maximum family. This is stated precisely in Theorem 1.6. We deduce some similar results for the more classical case of Erdős-Ko-Rado type theorems where all the sets in the family are restricted to be of a fixed size. See Corollary 1.7. The main technique that we apply is spectral analysis of intersection matrices that encode the relevant combinatorial information concerning intersecting families. An interesting twist is that part of the linear algebra involved is done over certain polynomial rings and not in the traditional setting over the reals. A crucial tool that we use is a recent result of Kindler and Safra [22] concerning Boolean functions whose Fourier transforms are concentrated on small sets. Research supported in part by the Israel Science Foundation, grant no. 0329745.     

Graphs of small dimensions

LetG=(V, E) be a graph withn vertices. The direct product dimension pdim (G) (c.f. [10], [12]) is the minimum numbert such thatG can be embedded into a product oft copies of complete graphsK _n.In [10], Lovász, Neetil and Pultr determined the direct product dimension of matchings and paths and gave sharp bounds for the product dimension of cycles, all logarithmic in the number of vertices.     

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.     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.