A classification of the structures of some Sperner families and superimposed codes

In this paper we will give a new proof by using group action to prove the uniqueness of maximal Sperner families of [n]. We will also prove the uniqueness of Sperner families F of [n] with by using a combinatorial approach. Furthermore, by using the uniqueness of Sperner family, we will classify all the structures of (1,2) superimposed codes of size 9×10 and 9×11.     

有限子集系的一个结果

１９８７年，黄国泰推广了Ｋｌｅｉｔｍａｎ和Ｋａｔｏｎａ定理。但是，若对某个正整数ｔ（１≤ｔ≤ｋ－１）不存在Ｆ中的两个元Ａ，Ｂ满足：存在某ｔ个Ｓｉ，使得Ｓｉ∩Ａ－Ｓｉ∩Ｂ，而对其余的ｋ－ｔ个Ｓｊ都有Ａ∩Ｓｊ     

Bounds on Maximal Families of Sets Not Containing Three Sets with A ∩ B ⊂ C, A ⊄ B

Lower and upper estimates are given on the size of a family of subsets of an n-element set containing no three distinct sets satisfying A ∩ B ⊂ C, A ⊄ B. This is a sharpening of an earlier result where the same question was solved under the condition that there are no three distinct sets such that A ∩ B ⊂ C. The second author was supported by the Hungarian National Foundation for Scientific Research grant numbers NK062321, AT048826, the Bulgarian National Science Fund under Grant IO-03/2005 and the projects of the European Community: INTAS 04-77-7171, FIST–MTKD-CT-2004-003006.     

Constructing and classifying neighborhood anti-Sperner graphs

For a simple graph G let N_G(u) be the (open) neighborhood of vertex u∈V(G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v∈V(G)?{u} with N_G(u)⊆N_G(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_H(u)≠N_H(v) when u≠v, for all u and v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69-77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r=0,1,…,6.