The quasi‐randomness of hypergraph cut properties

Let satisfy and suppose a k‐uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets of sizes , the number of edges intersecting is (asymptotically) the number one would expect to find in a random k‐uniform hypergraph. Can we then infer that H is quasi‐random? We show that the answer is negative if and only if . This resolves an open problem raised in 1991 by Chung and Graham [J AMS 4 (1991), 151–196]. While hypergraphs satisfying the property corresponding to are not necessarily quasi‐random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi‐random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Coloring uniform hypergraphs with few edges

A hypergraph is b‐simple if no two distinct edges share more than b vertices. Let m(r, t, g) denote the minimum number of edges in an r‐uniform non‐t‐colorable hypergraph of girth at least g. Erd?s and Lovász proved that A result of Szabó improves the lower bound by a factor of r^2?? for sufficiently large r. We improve the lower bound by another factor of r and extend the result to b‐simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed b, t, and ? > 0 and sufficiently large r, every r‐uniform b‐simple hypergraph with maximum edge‐degree at most t^rr^1?? is t‐colorable. Some results hold for list coloring, as well. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Random coloring method in the combinatorial problem of Erdős and Lovász

The work deals with a combinatorial problem of P. Erd?s and L. Lovász concerning simple hypergraphs. Let denote the minimum number of edges in an n‐uniform simple hypergraph with chromatic number at least . The main result of the work is a new asymptotic lower bound for . We prove that for large n and r satisfying the following inequality holds where . This bound improves previously known bounds for . The proof is based on a method of random coloring. We have also obtained results concerning colorings of h‐simple hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The size of minimum 3‐trees

A 3‐uniform hypergraph (3‐graph) is said to be tight, if for any 3‐partition of its vertex set there is a transversal triple. We give the final steps in the proof of the conjecture that the minimum number of triples in a tight 3‐graph on n vertices is exactly . © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 103–114, 2007     

On the linear arboricity of planar graphs

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ. The conjecture has been proved to be true for graphs having Δ = 1, 2, 3, 4, 5, 6, 8, 10. Combining these results, we prove in the article that the conjecture is true for planar graphs having Δ(G) ≠ 7. Several related results assuming some conditions on the girth are obtained as well. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 129–134, 1999     

Hamiltonian chains in hypergraphs

A cyclic ordering of the vertices of a k‐uniform hypergraph is called a hamiltonian chain if any k consecutive vertices in the ordering form an edge. For k = 2 this is the same as a hamiltonian cycle. We consider several natural questions about the new notion. The main result is a Dirac‐type theorem that provides a sufficient condition for finding hamiltonian chains in k‐uniform hypergraphs with large (k − 1)‐minimal degree. If it is more than than the hypergraph contains a hamiltonian chain. © 1999 Wiley & Sons, Inc. J Graph Theory 30: 205–212, 1999     

C‐perfect hypergraphs

Let ${\mathcal{H}}=({{X}},{\mathcal{E}})Let ${\mathcal{H}}=({{X}},{\mathcal{E}})$ be a hypergraph with vertex set X and edge set ${\mathcal{E}}$. A C‐coloring of ${\mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}\in{\mathcal{E}}$ (i.e. no edge is multicolored). We denote by $\bar{\chi}({\mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $\alpha({\mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}\in{\mathcal{E}}$, and $\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E \in {\mathcal{E}}$. The hypergraph ${\mathcal{H}}$ is called C‐perfect if $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$ holds for every induced subhypergraph ${\mathcal{H}}\prime\subseteq{\mathcal{H}}$. If ${\mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${\mathcal{H}}$ with $\tau({\mathcal{H}})\le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010     

Mean Ramsey–Turán numbers

A ρ‐mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most ρ. For a graph H and for ρ ≥ 1, the mean Ramsey–Turán number RT(n, H,ρ ? mean) is the maximum number of edges a ρ‐mean colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. It is conjectured that where is the maximum number of edges a k edge‐colored graph with n vertices can have under the condition it does not have a monochromatic copy of H. We prove the conjecture holds for . We also prove that . This result is tight for graphs H whose clique number equals their chromatic number. In particular, we get that if H is a 3‐chromatic graph having a triangle then . © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 126–134, 2006     

On the existence of a rainbow 1‐factor in 1‐factorizations of K

Let be a 1‐factorization of the complete uniform hypergraph with and . We show that there exists a 1‐factor of whose edges belong to n different 1‐factors in . Such a 1‐factor is called a “rainbow” 1‐factor or an “orthogonal” 1‐factor. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 487–490, 2007     

The linear arboricity of planar graphs of maximum degree seven is four

The linear arboricity of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama et al. conjectured that for any simple graph G. Wu wu proved the conjecture for a planar graph G of maximum degree . It is noted here that the conjecture is also true for . © 2008 Wiley Periodicals, Inc. J Graph Theory 58:210‐220, 2008     

The size‐Ramsey number of trees

Given a graph G, the size‐Ramsey number $\hat r(G)$ is the minimum number m for which there exists a graph F on m edges such that any two‐coloring of the edges of F admits a monochromatic copy of G. In 1983, J. Beck introduced an invariant β(·) for trees and showed that $\hat r(T) = \Omega (\beta (T))$ . Moreover he conjectured that $\hat r(T) = \Theta (\beta (T))$ . We settle this conjecture by providing a family of graphs and an embedding scheme for trees. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

The generalized Randić index of trees

The generalized Randi?; index of a tree T is the sum over the edges of T of where is the degree of the vertex x in T. For all , we find the minimal constant such that for all trees on at least 3 vertices, , where is the number of vertices of T. For example, when . This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with . More generally, fix and define , where is the number of leaves of T. We determine the best constant such that for all trees on at least 3 vertices, . Using these results one can determine (up to terms) the maximal Randi?; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

More on foxes

An edge in a k‐connected graph G is called k‐contractible if the graph obtained from G by contracting e is k‐connected. Generalizing earlier results on 3‐contractible edges in spanning trees of 3‐connected graphs, we prove that (except for the graphs if ) (a) every spanning tree of a k‐connected triangle free graph has two k‐contractible edges, (b) every spanning tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (c) for , every DFS tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (d) every spanning tree of a cubic 3‐connected graph nonisomorphic to K₄ has at least many 3‐contractible edges, and (e) every DFS tree of a 3‐connected graph nonisomorphic to K₄, the prism, or the prism plus a single edge has two 3‐contractible edges. We also discuss in which sense these theorems are best possible.     

The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets S ⊂ V (G) of size at most n/2, where ∂S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Minimum K2, 3‐Saturated Graphs

A graph is K_{2, 3}‐saturated if it has no subgraph isomorphic to K_{2, 3}, but does contain a K_{2, 3} after the addition of any new edge. We prove that the minimum number of edges in a K_{2, 3}‐saturated graph on vertices is sat.     

Extending the Erdős–Ko–Rado theorem

Let be a k‐uniform hypergraph on n vertices. Suppose that holds for all . We prove that the size of is at most if satisfies and n is sufficiently large. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Tiling 3‐Uniform Hypergraphs With

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).     

Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three

In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let and be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3‐uniform hypergraph of order at least 8 and with maximum degree at most three, then and there is a connected 3‐uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on vertices, where denotes the maximum degree in H, then and this bound is asymptotically best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory     

Construction of graphs with given circular flow numbers

Suppose r ≥ 2 is a real number. A proper r‐flow of a directed multi‐graph is a mapping such that (i) for every edge , ; (ii) for every vertex , . The circular flow number of a graph G is the least r for which an orientation of G admits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003