On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

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     

On the Choice Number of Packings

In this note, we show that for positive integers s and k, there is a function such that every t‐ packing with at least edges, , has choice number greater than s. Consequently, for integers s, k, t, and λ there is a such that every t‐ design with has choice number greater than s. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 504‐507, 2012     

Embedding Factorizations for 3‐Uniform Hypergraphs

In this article, two results are obtained on a hypergraph embedding problem. The proof technique is itself of interest, being the first time amalgamations have been used to address the embedding of hypergraphs. The first result finds necessary and sufficient conditions for the embedding a hyperedge‐colored copy of the complete 3‐uniform hypergraph of order m, , into an r‐factorization of , providing that . The second result finds necessary and sufficient conditions for an embedding when not only are the colors of the hyperedges of given, but also the colors of all the “pieces” of hyperedges on these m vertices are prescribed (the “pieces” of hyperedges are eventually extended to hyperedges of size 3 in by adding new vertices to the hyperedges of size 1 and 2 during the embedding process). Both these results make progress toward settling an old question of Cameron on completing partial 1‐factorizations of hypergraphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 216–224, 2013     

Density Conditions for Panchromatic Colourings of Hypergraphs

Let be a hypergraph. A panchromatic t-colouring of is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of is . Among other results, it is proved here that if every edge has at least t vertices and whenever , then is panchromatically t-choosable, and this condition is sharp; the minimum such that every t-uniform hypergraph with is panchromatically t-choosable satisfies ; and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if whenever , and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree. Received November 10, 1998 RID="*" ID="*" This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.     

The Average Degree of Minimally Contraction‐Critically 5‐Connected Graphs

An edge of a 5‐connected graph is said to be 5‐removable (resp. 5‐contractible) if the removal (resp. the contraction) of the edge results in a 5‐connected graph. A 5‐connected graph with neither 5‐removable edges nor 5‐contractible edges is said to be minimally contraction‐critically 5‐connected. We show the average degree of every minimally contraction‐critically 5‐connected graph is less than . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction‐critically 5‐connected graph whose average degree is greater than .     

Transversals in Uniform Hypergraphs with Property (p,2)

Dedicated to the memory of Paul Erdős Let f(r,p,t) (p > t >= 1, r >= 2) be the maximum of the cardinality of a minimum transversal over all r-uniform hypergraphs possessing the property that every subhypergraph of with p edges has a transversal of size t. The values of f(r,p,2) for p = 3, 4, 5, 6 were found in [1] and bounds on f(r,7,2) are given in [3]. Here we prove that for large p and huge r. Received September 23, 1999 RID="*" ID="*" This work was partially supported by the grant 99-01-00581 of the Russian Foundation for Fundamental Research and the Dutch–Russian Grant NWO-047-008-006.     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Detachments of Amalgamated 3‐Uniform Hypergraphs Factorization Consequences

A is a hypergraph obtained from by splitting some or all of its vertices into more than one vertex. Amalgamating a hypergraph can be thought of as taking , partitioning its vertices, then for each element of the partition squashing the vertices to form a single vertex in the amalgamated hypergraph . In this paper, we use Nash‐Williams lemma on laminar families to prove a detachment theorem for amalgamated 3‐uniform hypergraphs, which yields a substantial generalization of previous amalgamation theorems by Hilton, Rodger, and Nash‐Williams. To demonstrate the power of our detachment theorem, we show that the complete 3‐uniform n‐partite multihypergraph can be expressed as the union of k edge‐disjoint factors, where for , is ‐regular, if and only if:

1. for all ,
2. for each i, , and
3. .

     

Stability of solutions for a class of nonlinear cone constrained optimization problems,part 2: Application to parameter estimation

In this paper we study a problem of parameter estimation in two point boundary value problems. Using a stability theorem for nonlinear cone constrained optimization problems derived in Part 1 of this paper we investigate stability properties of the solutions of the parameter estimation problem in the output-least-squares formulation.     

Degree‐ and Orbit‐Balanced Γ‐Designs When Γ Has Five Vertices

A Γ‐design of the complete graph is a set of subgraphs isomorphic to Γ (blocks) whose edge‐sets partition the edge‐set of . is balanced if the number of blocks containing x is the same number of blocks containing y for any two vertices x and y. is orbit‐balanced, or strongly balanced, if the number of blocks containing x as a vertex of a vertex‐orbit A of Γ is the same number of blocks containing y as a vertex of A, for any two vertices x and y and for every vertex‐orbit A of Γ. We say that is degree‐balanced if the number of blocks containing x as a vertex of degree d in Γ is the same number of blocks containing y as a vertex of degree d in Γ, for any two vertices x and y and for every degree d in Γ. An orbit‐balanced Γ‐design is also degree‐balanced; a degree‐balanced Γ‐design is also balanced. The converse is not always true. We study the spectrum for orbit‐balanced, degree‐balanced, and balanced Γ‐designs of when Γ is a graph with five vertices, none of which is isolated. We also study the existence of balanced (respectively, degree‐balanced) Γ‐designs of which are not degree‐balanced (respectively, not orbit‐balanced).     

An exposá of the mullin-rota theory of polynomials of binomial type

The basic theorems of the Mullin-Rota theory of polynomials of binomial type are rederived here by a combination of the classical theory of generating functions and Rota's operator theoretical methods. As a result a certain number of new identities are obtained.     

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.     

On the third largest Laplacian eigenvalue of a graph

In this article, a sharp lower bound for the third largest Laplacian eigenvalue of a graph is given in terms of the third largest degree of the graph.     

On 5‐Cycles and 6‐Cycles in Regular n‐Tournaments

Let T be a tournament of order n and be the number of cycles of length m in T. For and odd n, the maximum of is achieved for any regular tournament of order n (M. G. Kendall and B. Babington Smith, 1940), and in the case it is attained only for the unique regular locally transitive tournament RLT_n of order n (U. Colombo, 1964). A lower bound was also obtained for in the class of regular tournaments of order n (A. Kotzig, 1968). This bound is attained if and only if T is doubly regular (when ) or nearly doubly regular (when ) (B. Alspach and C. Tabib, 1982). In the present article, we show that for any regular tournament T of order n, the equality holds. This allows us to reduce the case to the case In turn, the pure spectral expression for obtained in the class implies that for a regular tournament T of order the inequality holds, with equality if and only if T is doubly regular or T is the unique regular tournament of order 7 that is neither doubly regular nor locally transitive. We also determine the value of c₆(RLT_n) and conjecture that this value coincides with the minimum number of 6‐cycles in the class for each odd      

The 2‐Blocking Number and the Upper Chromatic Number of PG(2,q)

A twofold blocking set (double blocking set) in a finite projective plane Π is a set of points, intersecting every line in at least two points. The minimum number of points in a double blocking set of Π is denoted by τ₂(Π). Let PG(2,q) be the Desarguesian projective plane over GF(q), the finite field of q elements. We show that if q is odd, not a prime, and r is the order of the largest proper subfield of GF(q), then τ₂PG(2,q))≤ 2(q+(q‐1)/(r‐1)). For a finite projective plane Π, let denote the maximum number of classes in a partition of the point‐set, such that each line has at least two points in some partition class. It can easily be seen that (?) for every plane Π on v points. Let , p prime. We prove that for , equality holds in (?) if q and p are large enough.     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory