Polynomal-size Frege proofs of Bollobás’ theorem on the trace of sets. (English) Zbl 1157.03034

Summary: We show that Bollobás’ theorem on the trace of sets has polynomial-size Frege proofs.


03F20 Complexity of proofs
05D05 Extremal set theory
Full Text: DOI Euclid


[1] T. Arai, A bounded arithmetic AID for Frege systems, Ann. Pure Appl. Logic 103 (2000), nos. 1-3, 155-199. · Zbl 0959.03046 · doi:10.1016/S0168-0072(99)00041-X
[2] M. L. Bonet, S. R. Buss and T. Pitassi, Are there hard examples for Frege systems?, in Feasible mathematics, II (Ithaca, NY, 1992) , 30-56, Birkhäuser, Boston, Boston, MA, 1994. · Zbl 0834.03021 · doi:10.1007/978-1-4612-2566-9_3
[3] P. Frankl, On the trace of finite sets, J. Combin. Theory Ser. A 34 (1983), no. 1, 41-45. · Zbl 0505.05001 · doi:10.1016/0097-3165(83)90038-9
[4] P. Frankl, Extremal set systems, in Handbook of combinatorics, Vol. 1, 2 , 1293-1329, Elsevier, Amsterdam, 1995. · Zbl 0844.05094
[5] L. Lovász, Combinatorial problems and exercises , North-Holland, Amsterdam, 1979.
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.