Name
Abstract | ||
|---|---|---|
Let H be a simple hypergraph on the vertex set V and S⊆V. The trace of H on S is the (not necessarily simple) hypergraph obtained by intersecting the edges of H with the set S. The theorems of Bondy [J.A. Bondy, Induced subsets, J. Comb. Th. B 12 (1972) 201–202], Bollobás [B. Bollobás, unpublished, see in [L. Lovász, Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979] Problem 13.10], and Sauer [N. Sauer, On the density of families of sets, J. Comb. Th. A 13 (1972) 145–147] are dealing with the maximum number of distinct edges of certain traces. Frankl [P. Frankl, On the trace of finite sets, J. Comb. Th. A 34 (1983) 41–45] and Alon [N. Alon, On the density of sets of vectors, Discrete Mathematics 46 (1983) 199–202] gave a common generalization of these theorems. In this paper first we examine the multiplicity of edges of trace hypergraphs and show that there is a strong connection between this number and the number of distinct edges of traces (for a search theoretical application see [G. Wiener, Rounds in combinatorial search, submitted]). Then we give a common extension of this result and the abovementioned theorem of Frankl. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.endm.2007.07.076 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
hypergraph,trace,set system,hereditary hypergraph,edge multiplicity | Discrete mathematics,Combinatorics,Finite set,Vertex (geometry),Constraint graph,Hypergraph,Multiplicity (mathematics),Combinatorial search,Mathematics | Journal |
Volume | ISSN | Citations |
29 | 1571-0653 | 4 |
PageRank | References | Authors |
0.57 | 3 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Wiener | 1 | 64 | 10.65 |