On the Ramsey Number of Sparse 3-Graphs

We consider a hypergraph generalization of a conjecture of Burr and Erd?s concerning the Ramsey number of graphs with bounded degree. It was shown by Chvátal, Rödl, Trotter, and Szemerédi [The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), no. 3, 239–243] that the Ramsey number R(G) of a graph G of bounded maximum degree is linear in |V(G)|. We derive the analogous result for 3-uniform hypergraphs.     

Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

Embeddings and Ramsey numbers of sparse <Emphasis Type="Italic">κ</Emphasis>-uniform hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [3] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [6,23] the same result was proved for 3-uniform hypergraphs. Here we extend this result to κ-uniform hypergraphs for any integer κ ≥ 3. As in the 3-uniform case, the main new tool which we prove and use is an embedding lemma for κ-uniform hypergraphs of bounded maximum degree into suitable κ-uniform ‘quasi-random’ hypergraphs.     

Strong sufficient conditions for the existence of Hamiltonian circuits in undirected graphs

In this paper, we derive some results giving sufficient conditions for a graph G containing a Hamiltonian path to be Hamiltonian. In particular the Bondy-Chvátal theorem [J. A. Bondy and V. Chvátal, Discrete Math. 15 (1976), 111–135] is derived as a corollary of the main theorem of this paper and hence a more powerful closure operation than the one introduced by Bondy and Chvátal is defined. These results can be viewed as a step towards a unification of the various known results on the existence of Hamiltonian circuits in undirected graphs. Moreover, Theorem 1 of this paper provides a counterpart of the Chvátal-Erdös theorem [V. Chvátal and P. Erdös, Discrete Math. 2 (1972), 111–113] which gives a sufficient condition for a Hamiltonian circuit in terms of global vertex connectivity and independence number.     

Total domination of graphs and small transversals of hypergraphs

The main result of this paper is that every 4-uniform hypergraph on n vertices and m edges has a transversal with no more than (5n + 4m)/21 vertices. In the particular case n = m, the transversal has at most 3n/7 vertices, and this bound is sharp in the complement of the Fano plane. Chvátal and McDiarmid [5] proved that every 3-uniform hypergraph with n vertices and edges has a transversal of size n/2. Two direct corollaries of these results are that every graph with minimal degree at least 3 has total domination number at most n/2 and every graph with minimal degree at least 4 has total domination number at most 3n/7. These two bounds are sharp.     

The size of 3-uniform hypergraphs with given matching number and codegree

To determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvátal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear 3-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of 3-graphs with bounded codegree and matching number.     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Hypergraphs with large transversal number and with edge sizes at least four

Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.     

Vertex Arboricity and Vertex Degrees

The vertex arboricity of a graph G, denoted a(G), is the minimum number of subsets into which V(G) can be partitioned so that each subset induces an acyclic graph. We first give a vertex degree condition to guarantee \(a(G) \le k\), which is best possible in the same sense as Chvátal’s well-known hamiltonian degree condition. We then explore comparably strong degree conditions for \(a(G) \ge k\), and show that any such condition has intrinsic complexity which grows superpolynomially with the order of G.     

Asymptotic random graph intuition for the biased connectivity game

We study biased Maker/Breaker games on the edges of the complete graph, as introduced by Chvátal and Erd?s. We show that Maker, occupying one edge in each of his turns, can build a spanning tree, even if Breaker occupies b ≤ (1 ? o(1)) · edges in each turn. This improves a result of Beck, and is asymptotically best possible as witnessed by the Breaker‐strategy of Chvátal and Erd?s. We also give a strategy for Maker to occupy a graph with minimum degree c (where c = c(n) is a slowly growing function of n) while playing against a Breaker who takes b ≤ (1 ? o(1)) · edges in each turn. This result improves earlier bounds by Krivelevich and Szabó. Both of our results support the surprising random graph intuition: the threshold bias is asymptotically the same for the game played by two “clever” players and the game played by two “random” players. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Bounds for the ramsey number of a disconnected graph versus any graph

Bounds are determined for the Ramsey number of the union of graphs versus a fixed graph H, based on the Ramsey number of the components versus H. For certain unions of graphs, the exact Ramsey number is determined. From these formulas, some new Ramsey numbers are indicated. In particular, if . Where k_i is the number of components of order i and t₁ (H) is the minimum order of a color class over all critical colorings of the vertices of H, then .     

Small Chvátal Rank

We propose a variant of the Chvátal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x : A x ≤ b} as b varies. The number of steps needed is called the small Chvátal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.     

Optimizing over the first Chvátal closure

How difficult is, in practice, to optimize exactly over the first Chvátal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Can the first-closure optimization be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvátal-Gomory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvátal closure for a set of ILP problems from MIPLIB 3.0 and 2003. We also report, for the first time, the optimal solution of a very hard instance from MIPLIB 2003, namely nsrand-ipx, obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure.     

The hybrid set theory

We shall develop, in this paper, the hybrid set theory extending some notions of the hybrid real number system considered in [V. Lakshmikantham, D. Kovach, Hybrid real number system, Nonlinear Analysis: Hybrid Systems (2006), doi:10.1016/nahs.2006.07.001], so as to shed some light on the existing set theory and strengthen it. We shall also list some ideas of set theory that existed long before Cantor’s discovery [G. Cantor, Contributions to the Founding of the Theory of Transfinite Numbers (P.E.B., Trans.), The Open Court Publishing Co., la Salle, Illinois, 1952].     

A New Chvátal Type Condition for Pancyclicity

Schmeichel and Hakimi [5], and Bauer and Schmeichel [1] gave an evidence in support of the well-known Bondy’s “metaconjecture” that almost any non-trivial condition on graphs which implies that the graph is hamiltonian also implies that it is pancyclic. In particular, they proved that the metaconjecture is valid for Chvátal’s condition [3]. We slightly generalize their results giving a new Chvâtal type condition for pancyclicity.     

Minimum size transversals in uniform hypergraphs

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number τ(H)$\tau \left(H\right)$ of a hypergraph H$H$ is the minimum cardinality of a transversal in H$H$. A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvátal and McDiarmid (1992)  [3]) gave some upper bounds for τ(H)$\tau \left(H\right)$ in a uniform hypergraph H$H$ with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for τ(H)$\tau \left(H\right)$ which improve the bounds by Chvátal and McDiarmid.     

Comments on “Application of generalized differential transform method to multi-order fractional differential equations”, Vedat Suat Erturk,Shaher Momani,Zaid Odibat [Commun Nonlinear Sci Numer Simul 2008;13:1642–54]

In this note, we would like to point some similarities between the study [Erturk VS, Momani S, Odibat Z. Application of generalized differential transform method to multi-order fractional differential equations. Commun Nonlinear Sci Numer Simul. doi:10.1016/j.cnsns.2007.02.006] with the already existing one [Arikoglu A, Ozkol I. Solution of fractional differential equations by using differential transform method. Chaos Soliton Fract. 10.1016/j.chaos.2006.09.004].     

Lines in hypergraphs

One of the De Bruijn-Erd?s theorems deals with finite hypergraphs where every two vertices belong to precisely one hyperedge. It asserts that, except in the perverse case where a single hyperedge equals the whole vertex set, the number of hyperedges is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of simply described families, near-pencils and finite projective planes. Chen and Chvátal proposed to define the line uv in a 3-uniform hypergraph as the set of vertices that consists of u, v, and all w such that {u;v;w} is a hyperedge. With this definition, the De Bruijn-Erd?s theorem is easily seen to be equivalent to the following statement: If no four vertices in a 3-uniform hypergraph carry two or three hyperedges, then, except in the perverse case where one of the lines equals the whole vertex set, the number of lines is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of two simply described families. Our main result generalizes this statement by allowing any four vertices to carry three hyperedges (but keeping two forbidden): the conclusion remains the same except that a third simply described family, complements of Steiner triple systems, appears in the extremal case.