×

Disjoint representability of sets and their complements. (English) Zbl 1073.05066

For a hypergraph \(H\) and a set \(S\), the trace of \(H\) on \(S\) is the set of all intersections of edges of \(H\) with \(S\). The paper under review studies forbidden trace problems, i.e., find the largest hypergraph \(H\) that does not contain some list of forbidden configurations as traces. The authors focus on combinations of three forbidden configurations: the \(k\)-singleton \([k]^{ (1) }\), the \(k\)-co-singleton \([k]^{ (k-1) }\), and the \(k\)-chain \(\left\{ \emptyset, \left\{ 1 \right\} , [1,2], \dots, [1,k-1] \right\}\). Here we write \([k]^{ (j) }\) for the set of all \(j\)-subsets of \([k] = \left\{ 1, 2, \dots, k \right\}\).

MSC:

05D05 Extremal set theory
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlswede, R.; Khachatrian, L. H., Counterexample to the Frankl-Pach conjecture for uniform, dense families, Combinatorica, 17, 299-301 (1997) · Zbl 0886.05109
[2] Alon, N., On the density of sets of vectors, Discrete Math., 46, 199-202 (1983) · Zbl 0514.05003
[3] J. Balogh, B. Bollobás, Unavoidable traces of set systems, Combinatorica, to appear.; J. Balogh, B. Bollobás, Unavoidable traces of set systems, Combinatorica, to appear. · Zbl 1090.05034
[4] Frankl, P., On the traces of finite sets, J. Combin. Theory Ser. A, 34, 41-45 (1983) · Zbl 0505.05001
[5] Frankl, P.; Pach, J., On disjointly representable sets, Combinatorica, 4, 39-45 (1984) · Zbl 0534.05003
[6] Z. Füredi, J. Pach, Traces of finite sets: extremal problems and geometric applications, Extremal Problems for Finite Sets (Visegrád, 1991), Bolyai Society of Mathematical Studies, vol. 3, János Bolyai Math. Soc., Budapest, 1994, pp. 251-282.; Z. Füredi, J. Pach, Traces of finite sets: extremal problems and geometric applications, Extremal Problems for Finite Sets (Visegrád, 1991), Bolyai Society of Mathematical Studies, vol. 3, János Bolyai Math. Soc., Budapest, 1994, pp. 251-282.
[7] Füredi, Z.; Quinn, F., Traces of finite sets, Ars Combin., 18, 195-200 (1984) · Zbl 0557.05003
[8] Graham, R.; Rothschild, B.; Spencer, J., Ramsey Theory (1990), Wiley: Wiley New York
[9] Sauer, N., On the density of families of sets, J. Combin. Theory Ser. A, 13, 145-147 (1972) · Zbl 0248.05005
[10] Shelah, S., A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math., 41, 247-261 (1972) · Zbl 0239.02024
[11] Vapnik, V. N.; Chervonenkis, A. Ya., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264-280 (1971) · Zbl 0247.60005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.