×

A new lower bound based on Gromov’s method of selecting heavily covered points. (English) Zbl 1262.05151

Summary: Boros and Füredi (for \(d=2\)) and Bárány (for arbitrary \(d\)) proved that there exists a positive real number \(c_d\) such that for every set \(P\) of \(n\) points in \({\mathbf R}^d\) in general position, there exists a point of \({\mathbf R}^d\) contained in at least \(c_d \binom{n}{d+1}\) \(d\)-simplices with vertices at the points of \(P\). Gromov improved the known lower bound on \(c_d\) by topological means. Using methods from extremal combinatorics, we improve one of the quantities appearing in Gromov’s approach and thereby provide a new stronger lower bound on \(c_d\) for arbitrary \(d\). In particular, we improve the lower bound on \(c_3\) from \(0.06332\) to more than \(0.07480\); the best upper bound known on \(c_3\) being \(0.09375\).

MSC:

05D99 Extremal combinatorics
05C35 Extremal problems in graph theory
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)

References:

[1] Baber, R., Talbot, J.: Hypergraphs do jump. Comb. Probab. Comput. 20, 161-171 (2011) · Zbl 1213.05184 · doi:10.1017/S0963548310000222
[2] Bárány, I.: A generalization of Carathéodory’s theorem. Discrete Math. 40, 141-152 (1982) · Zbl 0492.52005 · doi:10.1016/0012-365X(82)90115-7
[3] Basit, A.; Mustafa, N. H.; Ray, S.; Raza, S., Improving the first selection lemma in ℝ3, 354-357 (2010), New York · Zbl 1284.68582
[4] Boros, E., Füredi, Z.: The number of triangles covering the center of an n-set. Geom. Dedic. 17, 69-77 (1984) · Zbl 0595.52002 · doi:10.1007/BF00181519
[5] Bukh, B.: A point in many triangles. Electron. J. Comb., 13, pp. Note 10 (2006), 3 pp. (electronic) · Zbl 1165.52301
[6] Bukh, B., Matoušek, J., Nivasch, G.: Stabbing simplices by points and flats. Discrete Comput. Geom. 43, 321-338 (2010) · Zbl 1186.52001 · doi:10.1007/s00454-008-9124-4
[7] Freedman, M., Lovász, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphism of graphs. J. Am. Math. Soc. 20, 37-51 (2007) (electronic) · Zbl 1107.05089 · doi:10.1090/S0894-0347-06-00529-7
[8] Gromov, M.: Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20, 416-526 (2010) · Zbl 1251.05039 · doi:10.1007/s00039-010-0073-8
[9] Grzesik, A.: On the maximum number of C5’s in a triangle-free graph (2011). arXiv:1102.0962. Submitted for publication
[10] Hatami, H., Hladký, J., Král’, D., Norine, S., Razborov, A.: Non-three-colorable common graphs exist (2011). arXiv:1105.0307. Submitted for publication · Zbl 1248.05090
[11] Hatami, H., Hladký, J., Král’, D., Norine, S., Razborov, A.: On the number of pentagons in triangle-free graphs (2011). arXiv:1102.1634. Submitted for publication · Zbl 1259.05087
[12] Hladký, J., Král’, D., Norine, S.: Counting flags in triangle-free digraphs (2009). arXiv:0908.2791. Submitted for publication · Zbl 1273.05107
[13] Karasev, R.N.: A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem. Discrete Comput. Geom. 47, 492-495 (2012) · Zbl 1237.05054 · doi:10.1007/s00454-011-9332-1
[14] Lovász, L., Szegedy, B.: Limits of dense graph sequences. J. Comb. Theory, Ser. B 96, 933-957 (2006) · Zbl 1113.05092 · doi:10.1016/j.jctb.2006.05.002
[15] Matoušek, J., Wagner, U.: On Gromov’s method of selecting heavily covered points (2011). arXiv:1102.3515. Submitted for publication · Zbl 1298.51027
[16] Razborov, A.: Flag algebras. J. Symb. Log. 72, 1239-1282 (2007) · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[17] Razborov, A.: On 3-hypergraphs with forbidden 4-vertex configurations. SIAM J. Discrete Math. 24, 946-963 (2010) · Zbl 1223.05204 · doi:10.1137/090747476
[18] Wagner, U.: On k-sets and applications. Ph.D. thesis, ETH Zürich (2003)
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.