Disjoint representability of sets and their complements

DOI10.1016/J.JCTB.2005.02.005MaRDI QIDQ2565684zbMATH OpenOpenAlexFDO

Authors József Balogh, Peter Keevash, Benny Sudakov

Publication date 28 September 2005

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2005.02.005

zbMATH Keywords

extremal problemsforbidden trace problemhypergraphset system

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05)

Review text

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\}\).

Recommendations

• Forbidding complete hypergraphs as traces
• Forbidding \(K_{2,t}\) traces in triple systems
• Traces of hypergraphs
• scientific article; zbMATH DE number 736296
• scientific article; zbMATH DE number 3887691

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Counterexample to the Frankl-Pach conjecture for uniform, dense families
• scientific article; zbMATH DE number 3887691 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 736296 (Why is no real title available?)
• On disjointly representable sets
• On the density of families of sets
• On the density of sets of vectors
• On the trace of finite sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unavoidable traces of set systems

Cited in

(10)

• \(l\)-trace \(k\)-Sperner families of sets
• Forbidding complete hypergraphs as traces
• scientific article; zbMATH DE number 1204008 (Why is no real title available?)
• scientific article; zbMATH DE number 1131173 (Why is no real title available?)
• scientific article; zbMATH DE number 1501844 (Why is no real title available?)
• Linear algebra methods for Forbidden configurations
• Disjoint essential sets of implicates of a CQ Horn function
• Pairwise intersections and forbidden configurations
• Disjoint unions of complete minors
• Minimum difference representations of graphs

This page was built for publication: Disjoint representability of sets and their complements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565684)