{"entities":{"Q6574401":{"pageid":14185556,"ns":120,"title":"Item:Q6574401","lastrevid":99840467,"modified":"2026-06-05T20:49:33Z","type":"item","id":"Q6574401","labels":{"en":{"language":"en","value":"New bounds for the same-type lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7882981"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$B46AB134-4A1E-4A74-8E72-4E79B2B7AA3C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"acd68f6d32648d2153f16f9d92b565066075577a","datavalue":{"value":{"text":"New bounds for the same-type lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6574401$70A5F668-6683-4199-B611-A9289DEA2799","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8ebbaf3725bd542072bed3a66a343dca0533e08a","datavalue":{"value":"1545.5201","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6574401$0608C8AD-EE23-475C-A450-E0DF7080AC15","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3f08f5a30fd2ba6d48bf2bbbd9e219bdffb70462","datavalue":{"value":"10.37236/12414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6574401$2774A48F-B77D-43EA-B79C-4044BBB3A4AD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"518e0f7acf819031e0f364a9043c47b119d7fa2e","datavalue":{"value":{"entity-type":"item","numeric-id":314396,"id":"Q314396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$6D753053-DBD6-4769-AE42-22C8AEB459EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e00d2fba9c78f0629d1fb62714e947e0ccd936e5","datavalue":{"value":{"entity-type":"item","numeric-id":6451788,"id":"Q6451788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$1678A248-B62C-408A-830F-93415EECB37B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$DCEA76E0-A267-4340-B0BC-A3B9AD8DA7AD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"38e2d7fad723ba8eab01170feeffeaccd39e07ce","datavalue":{"value":{"time":"+2024-07-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6574401$BE3D70E1-0D09-41A7-A86A-E67F852989A8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc249b28e842217f0e3a387f7c36cc2539f9e9d8","datavalue":{"value":"Sets \\(Y_1,\\dots, Y_{d+1}\\subset \\mathbb{R}^d\\) are said to have the \\textit{same-type property} if, for every choice of points \\(y_1 \\in Y_1,\\dots, y_{d+1} \\in Y_{d+1}\\), the orientation of the points \\(y_1,\\dots, y_{d+1}\\) is the same. More generally, the sets \\(Y_1,\\dots, Y_m \\) are said to have the same-type property if every \\(d + 1\\) of them do. A natural question is the following: given disjoint finite sets \\(X_1,\\dots ,X_m \\subset \\mathbb{R}^d\\) such that their union is in general position, are there large subsets \\(Y_i \\subseteq X_i\\) such that the sets \\(Y_1,\\dots, Y_m\\) have the same-type property? The same-type lemma proved by \\textit{I. B\u00e1r\u00e1ny} and \\textit{P. Valtr} [Discrete Comput. Geom. 19, No. 3, 335--342 (1998; Zbl 0914.52007)] states that each \\(Y_i\\) may be taken to have a positive fraction of points from the corresponding \\(X_i\\). How large could this fraction be? Formally, for disjoint sets \\(X_1,\\dots ,X_m \\subset \\mathbb{R}^d\\), whose union is in general position, let us denote by \\(c(X_1, \\dots ,X_m)\\) the largest constant \\(c\\) for which there exist \\(Y_1,\\dots, Y_m\\) having the same-type property and satisfying \\(Y_i \\subseteq X_i\\), \\(|Y_i| \\geq c|X_i|\\). For any fixed number \\(m\\) and dimension \\(d\\), denote by \\(c(m, d)\\) the infimum of \\(c\\) for all such configurations. The paper under review shows that for \\(d\\geq 2\\) and \\(m\\geq d\\), the constant \\(c(m,d)\\) depends polynomially from \\(m\\), if \\(d\\) is fixed, by showing the bounds \\(d^{-50d^3}m^{-d^2}\\leq c(m,d)\\leq d^dm^{-d}\\). In the past, polynomial bounds were known only in the case of equal sized \\(X_i\\) sets.\\N\\NAs the same type lemma is frequently used in discrete geometry, this extension is very relevant. A construction is given to show that polynomial dependence on \\(m\\) is unavoidable. An algorithm is presented to approximate \\(c(m, d)\\) within a prescribed error.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6574401$8E9B8585-6CB3-41C1-AB0A-718D1A1FEC60","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"706e08216f8d7e32a9bfdcc84aeeba4ad0f22d8d","datavalue":{"value":{"entity-type":"item","numeric-id":169304,"id":"Q169304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$182B00C4-0F5D-40CF-AA70-0D147D867C80","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b81fed1ca06e8930440f3ae2c1b914de465c5f39","datavalue":{"value":"52C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6574401$F09A78DF-71FD-463C-B16D-5D915D11BD66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b10ffd28cd5081f5618864ddd574d7cd207e02bf","datavalue":{"value":"52C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6574401$13016113-DE48-4C4C-942D-9D6FE9884B03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"048d498cf3693865e8c6532c64e81761eb10212d","datavalue":{"value":"7882981","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6574401$8D82DA54-E251-48E8-93CE-92C11B5295F1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da53bde0858bb23a52f3a9ab43af8ad3af5144e6","datavalue":{"value":"same-type property","type":"string"},"datatype":"string"},"type":"statement","id":"Q6574401$124B0EC2-0279-46DA-A604-015F2A6C8E09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a508b633c4570aeaf6c261b826f7f5513758cf9b","datavalue":{"value":"same-type lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q6574401$E1551ED2-7B8A-4059-B84F-4E9AC74F59C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df022f7950b6b2510ab9ff037fdfc623f6921567","datavalue":{"value":"polynomial partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q6574401$240F68C9-2D40-4895-881C-1D80AC104EBA","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$2393D177-EE0D-41DB-B5AC-EB6C09B6E48E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$6FD45B63-2F5C-46B0-B62F-D82061CFFDFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b2a8904f9e87ac5f1151901c07f3e6a9827b1c0","datavalue":{"value":{"entity-type":"item","numeric-id":1387842,"id":"Q1387842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$C3D35FA2-BE9A-4CE0-A396-A2A97A1CD789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95127141592e878799f1620a9e20ee4ed2d5aea0","datavalue":{"value":{"entity-type":"item","numeric-id":5906950,"id":"Q5906950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$FFC52414-308B-4B88-9284-F619D9FFD555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21fcf3dc0806c25c094c5a03a4a0b4dc940a08be","datavalue":{"value":{"entity-type":"item","numeric-id":2888867,"id":"Q2888867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$9B8460A3-D594-4CEB-B823-D48393F9902E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8b877b4d68c220930a94298ab8d23efea52dcfc","datavalue":{"value":{"entity-type":"item","numeric-id":2956040,"id":"Q2956040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$8E242E1D-BFA7-40C2-8C3C-FD189B0C528D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ea301c5a1dedcc59977d51e75e13ea6405abd6f","datavalue":{"value":{"entity-type":"item","numeric-id":482909,"id":"Q482909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$CE1E03FC-BCBF-43D5-BF28-0A918FBB2191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201456419147dc91ada3d181f3a614aef90c103a","datavalue":{"value":{"entity-type":"item","numeric-id":714991,"id":"Q714991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$7507A413-BF9B-4E65-8041-16D67EDAC3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"561f8b7a7fcbc54a471becc49f3d9cdf14eea6b4","datavalue":{"value":{"entity-type":"item","numeric-id":452006,"id":"Q452006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$B13B4463-0ACC-4206-BC95-DC16B6149065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cae47064c63d30bafe36c9219eab3baab345830","datavalue":{"value":{"entity-type":"item","numeric-id":4530626,"id":"Q4530626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$0FEA8105-CBB8-4246-91C1-D6433508BB8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"038928ddb4bb70fd96309312d60af9cf3ef867fe","datavalue":{"value":{"entity-type":"item","numeric-id":2286590,"id":"Q2286590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$9C9F21E5-0F2B-4C6E-B0DF-03BAA901492D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a79f314812501b1a7ff2252e66e346a79513313f","datavalue":{"value":{"entity-type":"item","numeric-id":1388134,"id":"Q1388134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$BA2A6D0B-6A5B-4EA7-B934-4AA2DBBB3F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0858169259323e0073eb39af0e5ebaf607e9ee3","datavalue":{"value":{"entity-type":"item","numeric-id":5953378,"id":"Q5953378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$6903C5C5-AC5D-42E3-B53D-40063694ABE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a55b3cad03707f063097f9987057480554099f6","datavalue":{"value":{"entity-type":"item","numeric-id":1864120,"id":"Q1864120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$4E296675-F869-4447-B7D6-F6BDCB1C1C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae8aa99fea269dd328651f815c4f4c75fe7db260","datavalue":{"value":{"entity-type":"item","numeric-id":5280069,"id":"Q5280069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$3A10F62E-7A39-44BF-AA24-3E8E1FD89693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8be9375a315209f41df1b38374a5e7e956d28bf","datavalue":{"value":{"entity-type":"item","numeric-id":5807665,"id":"Q5807665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$0A368024-CFC6-4AB1-896D-E79F1866B752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6574401$94D3FBE7-B5E2-4FB3-B31A-E5D978CCB074","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33d759e46311b1c1fe61b8f2d7331fd6c2f2d15d","datavalue":{"value":{"entity-type":"item","numeric-id":5748883,"id":"Q5748883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"506e526dab14753d8492d90fad4dd9c65433b4be","datavalue":{"value":{"amount":"+0.7394343018531799","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6574401$EB00D14B-3999-41B1-BF71-7D9B23EAC5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c38d0574be3be43d63c6c14edce2c86c7ba1aed","datavalue":{"value":{"entity-type":"item","numeric-id":1387842,"id":"Q1387842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f3845ff22b753cb91deb218d0d97de7a6dfb07f","datavalue":{"value":{"amount":"+0.7386856079101562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6574401$BA8659FE-A361-4023-B9BA-7EAB81269207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b25e66be6ec077fae73058a09204622ad34313e2","datavalue":{"value":{"entity-type":"item","numeric-id":3602879,"id":"Q3602879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f731d1fbe94003bb82649b16b8346f89fd8a795f","datavalue":{"value":{"amount":"+0.7309963703155518","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6574401$9C97F3F6-4F02-48F9-ACB5-0C4B49CE841D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4ffa6662f2a7cfe7b4f8d84a144ab542ee344f2","datavalue":{"value":{"entity-type":"item","numeric-id":3191153,"id":"Q3191153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55d1a55a6f201e673f16e32ac02ef0279ec72fb3","datavalue":{"value":{"amount":"+0.7303543090820312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6574401$4930E755-B3F1-4FFF-9906-F60232EF2430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8359f1ff9da034c43ed8cd67d21780c6a51877e3","datavalue":{"value":{"entity-type":"item","numeric-id":2956040,"id":"Q2956040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab8031cd3af9c8b574494cd3498f9cfc614fd361","datavalue":{"value":{"amount":"+0.7237328886985779","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6574401$7AA10E59-883F-4DA5-9AE6-23C03432E6A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New bounds for the same-type lemma (scientific article; zbMATH DE number 7882981)","badges":[]}}}}}