Sparse color-critical graphs and hypergraphs with no short cycles

We give constructions of color-critical graphs and hypergraphs with no short cycles and with relatively few edges. In particular, we show that, for each n ≧ 3, the smallest number of edges in a 3-critical triangle-free n-graph (hypergraph) with m vertices is m + o(m) as m → ∞. Also, for each r ≧ 4, there exists an r-critical triangle-free 2-graph (graph) with m vertices and at most (r ? (7/3))m + o(m) edges. Weaker results are obtained for the existence of r-critical graphs containing no cycle of length at most / > 3.     

Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs

Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least (1-e)( *20c nr)(1-\varepsilon)\left( {\begin{array}{*{20}c} n\\ r\\ \end{array}}\right) edges, the 2-shadow has a monochromatic matching covering all but at most o(n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1))n in every (r – 1)-coloring of the edges of K^(r)_n{K^{(r)}_{n}}, the complete r-uniform hypergraph on n vertices.     

Conditions for -graphic sequences to be potentially -graphic

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544].     

On Ramsey—Turán type theorems for hypergraphs

LetH ^r be anr-uniform hypergraph. Letg=g(n;H ^r ) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH ^r . Lete =f(n;H ^r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH ^r . We show that ifr>2 andH ^r is e.g. a complete graph then $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$ while for someH ^r with \(\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0\) $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$ . This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.     

On claws belonging to every tournament

A directed graph is said to ben-unavoidable if it is contained as a subgraph by every tournament onn vertices. A number of theorems have been proven showing that certain graphs aren-unavoidable, the first being Rédei's results that every tournament has a Hamiltonian path. M. Saks and V. Sós gave more examples in [6] and also a conjecture that states: Every directed claw onn vertices such that the outdegree of the root is at most [n/2] isn-unavoidable. Here a claw is a rooted tree obtained by identifying the roots of a set of directed paths. We give a counterexample to this conjecture and prove the following result:any claw of rootdegreen/4 is n-unavoidable.     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Edge-maximal (k,i)-graphs

A graph G is a (k, l)-graph if for any subgraph H of G, that |V(H)| ≧ implies that k(H) ≦ k ? 1. An edge-maximal (k, l-graph G is one such that for any e ? E(G^c), G + e is not a (k, l)-graph. In [F. T. Boesch and J. A. M. McHugh, ?An Edge Extremal Result for Subcohesion,”? Journal of Combinatorial Theory B, vol. 38 (1985), pp. 1–7] a class of edge-maximal graphs was found and used to show best possible upper bounds of the size of edge-maximal (k, l)-graphs. In this paper, we investigate the lower bounds of the size of edge-maximal (k, l)-graphs. Let f(n, k, l) denote the minimum size of edge-maximal (k, l)-graphs of order n. We shall give a characterization of edge-maximal (k, l)-graphs. This characterization is used to determine f(n, k, l) and to characterize the edge-maximal (k, l)-graphs with minimum sizes, for all n ≦ k + 2 ≦ 5. Thus prior results in [F.T. Boesch and J. A. M. McHugh, op. cit.; H.-J. Lai, ?The Size of Strength-Maximal Graphs,”? Journal of Graph Theory, vol. 14 (1990), pp. 187–197] are extended.     

Covering a graph by topological complete subgraphs

Every graph onn vertices can be covered byex(n, TK ₄ ) =2n – 3 TK ₄ -subgraphs and edges. A similar result might hold for arbitrary topological (complete) subgraphs as indicated by the following result: Every graph onn vertices can be covered by 65ex(n, TK _p )TK _p -subgraphs and edges. IfH is a connected graph (|H| 3) then every graph onn vertices can be covered by 400ex(n, TH) TH-subgraphs and edges. Similar questions for coverings by odd and even cycles are also considered.This author's work was done while he was a guest at the Hungarian Academy of Sciences.     

Uniform Families and Count Matroids

Given an r-graph G on [n], we are allowed to add consecutively new edges to it provided that every time a new r-graph with at least l edges and at most m vertices appears. Suppose we have been able to add all edges. What is the minimal number of edges in the original graph? For all values of parameters, we present an example of G which we conjecture to be extremal and establish the validity of our conjecture for a range of parameters. Our proof utilises count matroids which is a new family of matroids naturally extending that of White and Whiteley. We characterise, in certain cases, the extremal graphs. In particular, we answer a question by Erdős, Füredi and Tuza. Received: May 6, 1998 Final version received: September 1, 1999     

On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.     

Linking (n − 2)-dimensional panels inn-space I: (k − 1,k)-graphs and (k − 1,k)-frames

A (k – 1,k)-graph is a multi-graph satisfyinge (k – 1)v – k for every non-empty subset ofe edges onv vertices, with equality whene = |E(G)|. A (k – 1,k)-frame is a structure generalizing an (n – 2, 2)-framework inn-space, a structure consisting of a set of (n – 2)-dimensional bodies inn-space and a set of rigid bars each joining a pair of bodies using ball joints. We prove that a graph is the graph of a minimally rigid (with respect to edges) (k – 1,k)-frame if and only if it is a (k – 1,k)-graph. Rigidity here means infinitesimal rigidity or equivalently statical rigidity.     

Subdivisions of Transitive Tournaments

We prove that, for r ≥ 2 andn ≥ n(r), every directed graph with n vertices and more edges than the r -partite Turán graph T(r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations ofT (r, n) induced by orderings of the vertex classes.     

On the greatest number of 2 and 3 colorings of a (v,e)-graph

Let F denote the family of simple undirected graphs on v vertices having e edges ((v, e)-graphs) and P(λ, G) be the chromatic polynomial of a graph G. For the given integers v, e, Δ, let f(v, e, Δ) denote the greatest number of proper colorings in Δ or less colors that a (v, e)-graph G can have, i.e., f(v, e, Δ) = max{P(Δ, G): G ∈ F}. In this paper we determine f(v, e, 2) and describe all graphs G for which P(2, G) = f(v, e, 2). For f(v, e, 3), a lower bound and an upper bound are found.     

Ramsey‐type results for Gallai colorings

A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐colorings of the edges of complete graphs. They actually turn out to be close to 2‐colorings—without being trivial extensions. Here, we give a method to extend some results on 2‐colorings to Gallai‐colorings, among them known and new, easy and difficult results. The method works for Gallai‐extendible families that include, for example, double stars and graphs of diameter at most d for 2?d, or complete bipartite graphs. It follows that every Gallai‐colored K_n contains a monochromatic double star with at least 3n+ 1/4 vertices, a monochromatic complete bipartite graph on at least n/2 vertices, monochromatic subgraphs of diameter two with at least 3n/4 vertices, etc. The generalizations are not automatic though, for instance, a Gallai‐colored complete graph does not necessarily contain a monochromatic star on n/2 vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization. We also investigate Ramsey numbers of graphs in Gallai‐colorings with a given number of colors. For any graph H let RG(r, H) be the minimum m such that in every Gallai‐coloring of K_m with r colors, there is a monochromatic copy of H. We show that for fixed H, RG (r, H) is exponential in r if H is not bipartite; linear in r if H is bipartite but not a star; constant (does not depend on r) if H is a star (and we determine its value). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

Structure of independent sets in direct products of some vertex-transitive graphs

Let Circ( r, n) be a circular graph. It is well known that its independence number α(Circ(r, n)) = r. In this paper we prove that α(Circ(r, n) × H ) = max{r|H |, nα(H )} for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ(r, n) × H. As consequences, we prove α(G × H ) = max{α(G)|V (H )|, α(H )|V (G)|} for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs

The main question discussed in this paper is how well a finite metric space of size n can be embedded into a graph with certain topological restrictions. The existing constructions of graph spanners imply that any n -point metric space can be represented by a (weighted) graph with n vertices and n ^{1 +O(1/r)} edges, with distances distorted by at most r . We show that this tradeoff between the number of edges and the distortion cannot be improved, and that it holds in a much more general setting. The main technical lemma claims that the metric space induced by an unweighted graph H of girth g cannot be embedded in a graph G (even if it is weighted) of smaller Euler characteristic, with distortion less than g/4 - 3/2 . In the special case when |V(G)| =|V(H)| and G has strictly less edges than H , an improved bound of g/3 - 1 is shown. In addition, we discuss the case χ(G) < χ(H) - 1 , as well as some interesting higher-dimensional analogues. The proofs employ basic techniques of algebraic topology. Received September 26, 1995, and in revised form March 18, 1996.     

Decomposition of the completer-graph into completer-partiter-graphs

Forn ≥ r ≥ 1, letf _r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf ₂(n) =n ? 1. Here we observe thatf ₃(n) =n ? 2 and show that for every fixedr ≥ 2, there are positive constantsc ₁(r) andc ₂(r) such thatc ₁(r) ≤f _r (n)?n ^?[r/2] ≤n ₂(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.     

The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

LetH be a fixed graph of chromatic numberr. It is shown that the number of graphs onn vertices and not containingH as a subgraph is . Leth _r (n) denote the maximum number of edges in anr-uniform hypergraph onn vertices and in which the union of any three edges has size greater than 3r – 3. It is shown thath _r (n) =o(n ²) although for every fixedc < 2 one has lim _n h _r (n)/n ^c = .