Orderings of uniquely colorable hypergraphs

For a mixed hypergraph H=(X,C,D), where C and D are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every C∈C meets some class in more than one vertex, and every D∈D has a nonempty intersection with at least two classes. A vertex-orderx₁,x₂,…,x_n on X (n=|X|) is uniquely colorable if the subhypergraph induced by {x_j:1?j?i} has precisely one coloring, for each i (1?i?n). We prove that it is NP-complete to decide whether a mixed hypergraph admits a uniquely colorable vertex-order, even if the input is restricted to have just one coloring. On the other hand, via a characterization theorem it can be decided in linear time whether a given color-sequence belongs to a mixed hypergraph in which the uniquely colorable vertex-order is unique.     

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     

关于不含k-C-圈的n阶r-一致超图的若干结果

主要讨论了不含k-C-圈的n阶r-一致超图,对不同的k,分别得出了它的极大边数的一个下界,并且得出在有些情况下它的下界是最大的.另外,我们得到了Krn含k-C-圈的一个充分必要条件.     

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.     

超图结构上合作博弈的赋权Position值

在合作博弈的一般模型中总是假设所有联盟都能形成。不过,在实际中由于受到一些因素的制约,有些联盟是不能形成的。基于此,Myerson提出了具有图通讯结构的合作博弈。Myerson值和Position值是超图博弈上的两个重要分配规则。2005年,Slikker给出了在图博弈上Position值的公理化刻画。但超图博弈上Position值的公理化刻画一直悬而未决。本文通过引入“赋权平衡超边贡献公理”,并结合经典的“分支有效性”,提出了超图博弈上赋权Position值的公理化刻画。作为推论,解决了超图博弈上Position值的公理化刻画问题。     

Embedding hypertrees into steiner triple systems

In this paper, we are interested in the following question: given an arbitrary Steiner triple system on vertices and any 3‐uniform hypertree on vertices, is it necessary that contains as a subgraph provided ? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive.     

最大边连通和super-边连通超图的充分条件

设H是连通超图。若超图H的边连通度等于其最小度,则称H是最大边连通的。若超图H的每个最小边割总是由关联于某个最小度顶点的边集所构成,则称H是super-边连通的。首先给出一致线性超图是最大边连通超图的度序列条件。其次,给出一致线性超图是super-边连通超图的度条件。这些结果分别推广了Dankelmann和Volkmann（1997）以及Hellwig和Volkmann（2005）在图上的相关结论。     

Piercing random boxes

Consider a set of n random axis parallel boxes in the unit hypercube in ${\bf R}^{d}$ , where d is fixed and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least $\Omega_d(\sqrt{n}(\log n)^{d/2-1})$ and at most $O_d(\sqrt{n}(\log n)^{d/2-1}\log \log n)$ . © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 365–380, 2011