Max Horn SAT and the minimum cut problem in directed hypergraphs

In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definitions of hyperpath weight. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provides an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Circular mixed hypergraphs II:The upper chromatic number

A mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C, D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:X→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. A mixed hypergraph H is called circular if there exists a host cycle on the vertex set X such that every edge (C- or D-) induces a connected subgraph of this cycle.We suggest a general procedure for coloring circular mixed hypergraphs and prove that if H is a reduced colorable circular mixed hypergraph with n vertices, upper chromatic number and sieve number s, then

     

Flow hypergraph reducibility

Reducible flowgraphs were first defined by Allen in terms of intervals; another definition based on two flowgraph transformations was presented by Hecht and Ullman. In this paper, we extend the notion of reducibility to directed hypergraphs, proving that the interval and the transformation approaches preserve the equivalence when applied to this family.     

Matchings in hypergraphs of large minimum degree

It is well known that every bipartite graph with vertex classes of size n whose minimum degree is at least n/2 contains a perfect matching. We prove an analog of this result for hypergraphs. We also prove several related results that guarantee the existence of almost perfect matchings in r‐uniform hypergraphs of large minimum degree. Our bounds on the minimum degree are essentially best possible. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 269–280, 2006     

Hamilton cycles in quasirandom hypergraphs

We show that, for a natural notion of quasirandomness in k‐uniform hypergraphs, any quasirandom k‐uniform hypergraph on n vertices with constant edge density and minimum vertex degree Ω(n^k‐1) contains a loose Hamilton cycle. We also give a construction to show that a k‐uniform hypergraph satisfying these conditions need not contain a Hamilton ?‐cycle if k– ? divides k. The remaining values of ? form an interesting open question. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 363–378, 2016     

On independent sets in hypergraphs

The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove that if H_n is an n‐vertex ‐uniform hypergraph in which every r‐element set is contained in at most d edges, where , then where satisfies as . The value of c_r improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi (J Comb Theory Ser A 32 (1982), 321–335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269–271) and Alon (Random Struct Algorithms 9 (1996), 271–278). The above statement is close to best possible, in the sense that for each and all values of , there are infinitely many H_n such that where depends only on r. In addition, for many values of d we show as , so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224‐239, 2014     

Tight Hamilton cycles in random uniform hypergraphs

In this paper we show that e/n is the sharp threshold for the existence of tight Hamilton cycles in random k ‐uniform hypergraphs, for all k ≥ 4. When k = 3 we show that 1/n is an asymptotic threshold. We also determine thresholds for the existence of other types of Hamilton cycles. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Powers of tight Hamilton cycles in randomly perturbed hypergraphs

For k ≥ 2 and r ≥ 1 such that k + r ≥ 4, we prove that, for any α > 0, there exists ε > 0 such that the union of an n‐vertex k‐graph with minimum codegree and a binomial random k‐graph with on the same vertex set contains the rth power of a tight Hamilton cycle with high probability. This result for r = 1 was first proved by McDowell and Mycroft.     

Hypernetworks in a directed hypergraph

Recently novel distributed approaches to the formation of collaborative networked organizations have been proposed. Some of them make use of logical–formal structures (i.e., hypernetworks and hyperpaths) based on concepts related to directed hypergraphs in order to formally represent competitive inter-cluster and collaborative intra-cluster relationships.     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

On Graph-Lagrangians and clique numbers of 3-uniform hypergraphs

The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs.Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques.This connection provided a new proof of Turán classical result on the Turán density of complete graphs.Since then,Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs.Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range.They showed that if G is a 3-uniform graph with m edges containing a clique of order t-1,then λ(G)=λ([t-1]~((3))) provided (t-13)≤m≤(t-13)+_(t-22).They also conjectured:If G is an r-uniform graph with m edges not containing a clique of order t-1,then λ(G)λ([t-1]~((r))) provided (t-1r)≤ m ≤(t-1r)+(t-2r-1).It has been shown that to verify this conjecture for 3-uniform graphs,it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m=t-13+t-22.Regarding this conjecture,we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t-1]~((3))\E(G)|=p,then λ(G)λ([t-1]~((3))) provided m=(t-13)+(t-22) and t≥17p/2+11.     

The chromatic numbers of random hypergraphs

For a pair of integers 1≤γ<r, the γ-chromatic number of an r-uniform hypergraph H=(V, E) is the minimal k, for which there exists a partition of V into subsets T₁,…,T_k such that |e∩T_i|≤γ for every e∈E. In this paper we determine the asymptotic behavior of the γ-chromatic number of the random r-uniform hypergraph H_r(n, p) for all possible values of γ and for all values of p down to p=Θ(n^−r+1). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998     

Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs

For positive integers r>?, an r‐uniform hypergraph is called an ?‐cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of r consecutive vertices, and such that every pair of consecutive edges (in the natural ordering of the edges) intersect in precisely ? vertices; such cycles are said to be linear when ?=1, and nonlinear when ?>1. We determine the sharp threshold for nonlinear Hamiltonian cycles and show that for all r>?>1, the threshold for the appearance of a Hamiltonian ?‐cycle in the random r‐uniform hypergraph on n vertices is sharp and given by for an explicitly specified function λ. This resolves several questions raised by Dudek and Frieze in 2011.10     

List coloring triangle‐free hypergraphs

A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with , and . Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number . Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every linear (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number . The restriction to linear triple systems was crucial to their proof. We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the linear restriction from 8 , while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erd?s, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs. As an application, we prove that if is the collection of 3‐uniform triangles, then the Ramsey number satisfies for some positive constants a and b. The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that where C₃ is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015     

Coloring uniform hypergraphs with few colors

Let m(r, k) denote the minimum number of edges in an r‐uniform hypergraph that is not k‐colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2ⁿ, then m(r, k) ≥ ?(k)k^r(r/ln r)^n/(n+1). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004