Quasi-random hypergraphs

We introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi-random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of ways.     

Packing perfect matchings in random hypergraphs

We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer , the binomial ‐uniform random hypergraph contains edge‐disjoint perfect matchings, provided , where is an integer depending only on . Our result for is asymptotically optimal and for is optimal up to the factor. This significantly improves a result of Frieze and Krivelevich.     

Counting dense connected hypergraphs via the probabilistic method

In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o(n)). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.     

On the connectivity of proper colorings of random graphs and hypergraphs

Let Ω_q=Ω_q(H) denote the set of proper [q]‐colorings of the hypergraph H. Let Γ_q be the graph with vertex set Ω_q where two colorings σ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_n,m;k, k ≥ 2, the random k‐uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Γ_q is connected if d is sufficiently large and . This is optimal up to the first order in d. Furthermore, with a few more colors, we find that the diameter of Γ_q is O(n) w.h.p., where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber dynamics Markov Chain on Ω_q is ergodic w.h.p.     

Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, together with integers s_i and t_i (1≤s_i≤t_i≤|E_i|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge E_i satisfies s_i≤|φ(E_i)|≤t_i, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge E_i induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (s_i,t_i)=(2,|E_i|), while ‘C-edge’ assumes (s_i,t_i)=(1,|E_i|−1)-the differences are rather significant.     

Complex martingales and asymptotic enumeration

Many enumeration problems in combinatorics, including such fundamental questions as the number of regular graphs, can be expressed as high‐dimensional complex integrals. Motivated by the need for a systematic study of the asymptotic behavior of such integrals, we establish explicit bounds on the exponentials of complex martingales. Those bounds applied to the case of truncated normal distributions are precise enough to include and extend many enumerative results of Barvinok, Canfield, Gao, Greenhill, Hartigan, Isaev, McKay, Wang, Wormald, and others. Our method applies to sums as well as integrals. As a first illustration of the power of our theory, we considerably strengthen existing results on the relationship between random graphs or bipartite graphs with specified degrees and the so‐called β‐model of random graphs with independent edges, which is equivalent to the Rasch model in the bipartite case.     

Oriented hypergraphs: Balanceability

An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.     

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     

List colorings of multipartite hypergraphs

Let χ_l(G) denote the list chromatic number of the r‐uniform hypergraph G. Extending a result of Alon for graphs, Saxton and the second author used the method of containers to prove that, if G is simple and d‐regular, then . To see how close this inequality is to best possible, we examine χ_l(G) when G is a random r‐partite hypergraph with n vertices in each class. The value when r = 2 was determined by Alon and Krivelevich; here we show that almost surely, where d is the expected average degree of G and . The function g(r,α) is defined in terms of “preference orders” and can be determined fairly explicitly. This is enough to show that the container method gives an optimal lower bound on χ_l(G) for r = 2 and r = 3, but, perhaps surprisingly, apparently not for r ≥ 4.     

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     

Color critical hypergraphs with many edges

We show that for all k ≥ 3, r > l ≥ 2 there exists constant c = c(k, r, l) such that for large enough n there exists a k‐color‐critical r‐uniform hypergraph on less than n vertices, having more than cn^l edges, and having no l‐set of vertices occuring in more than one edge. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 56–74, 2006     

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.     

The VC dimension of k‐uniform random hypergraphs

A set of vertices is shattered in a hypergraph if any of its subsets is obtained as the intersection of an edge with the set. The VC dimension is the size of the largest shattered subset. Under the binomial model of k‐uniform random hypergraphs, the threshold function for the VC dimension to be larger than a given integer is obtained. The same is done for the testing dimension, which is the largest integer d such that all sets of cardinality d are shattered. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

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     

5-一致超图的全横贯

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.     

Judicious bisection of hypergraphs

Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously.In this paper,we prove that if G is a hypergraph with n vertices and m_i edges of size i for i=1,2,...,k,then G admits a bisection in which each vertex class spans at most(m_1)/2+1/4m_2+…+(1/(2~k)+m_k+o(m_1+…+m_k) edges,where G is dense enough or △(G)= o(n) but has no isolated vertex,which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.     

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     

Atomic decompositions of Banach-spacevalued martingales

Several theorems for atomic decompositions of Banach-space-valued martingales are proved. As their applications, the relationship among some martingale spaces such asH _α(X) and_ρ H _α in the case 0< α⩽ are studied. It is shown that there is a close connection between the results and the smoothness and convexity of the value spaces. Project supported by the National Natural Science Foundation of China (Grant No. 19771063).