{"entities":{"Q5954318":{"pageid":8131120,"ns":120,"title":"Item:Q5954318","lastrevid":40303543,"modified":"2025-02-22T09:28:18Z","type":"item","id":"Q5954318","labels":{"en":{"language":"en","value":"Holes in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1699543"}},"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":"Q5954318$7DA31654-361D-42F6-8F5C-5C4D0332A8EF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f7672d7363c6e540b8322bcc7cea5166cbd55596","datavalue":{"value":{"text":"Holes in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5954318$7F00BE6C-1D65-4987-AA02-AD43C126DA61","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b73b562385f15bc5ee0c4b4352af5a65422fb25","datavalue":{"value":"0992.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954318$D77BDC0D-DFC5-41C7-9103-79CF2FC74661","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"710a180755857dbcb451ea2f740500cb57b6456a","datavalue":{"value":{"entity-type":"item","numeric-id":326972,"id":"Q326972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954318$C137F05B-5D8B-47E2-B18B-0F634CAEAA13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954318$F9FCD354-9A74-464B-A2C3-6EA352A63CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dc0952d447fed38177fb32bd92c2d18011c79ac","datavalue":{"value":{"entity-type":"item","numeric-id":226978,"id":"Q226978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954318$5EDB628C-EA4A-4A58-BDC1-C008A90A9369","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":"Q5954318$70736D2E-A5C7-4063-8659-9E4BE795B4C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a58c0c334590fe3ab2e759e1b681637074ea80c2","datavalue":{"value":{"time":"+2002-02-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5954318$8DEC0B6C-FC02-436F-A2EE-C6F3F885C13B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b46d59f6a7382ccc34e084f478f5e839d593beb1","datavalue":{"value":"https://eudml.org/doc/121976","type":"string"},"datatype":"url"},"type":"statement","id":"Q5954318$6D54DFFC-015F-4EAB-B667-E617A8EF237C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4a4eb055ffe6414725d927a958ebf48ec46b7b1f","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r1.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q5954318$752A7E69-951C-4163-9857-BC065C330F73","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb6e22cb234a12887d28a3be5bc0a793929353f2","datavalue":{"value":"In variation of Szemer\u00e9di's regularity lemma (for this see [\\textit{J. Koml\u00f3s} and \\textit{M. Simonovits}, Bolyai Soc. Math. Stud. 2, 295-352 (1996; Zbl 0851.05065)]) the authors ask for a large nearly regular subgraph instead of a partition into nearly regular parts: In a bipartite graph \\(G= (V_1,V_2; E)\\) the density of a pair \\(U_1\\subseteq V_1\\), \\(U_2\\subseteq U_2\\) is defined as \\(d(U_1, U_2)= e(U_1, U_2)\\cdot|U_1|^{-1}\\cdot |U_2|^{- 1}\\) (\\(e\\) denoting the number of edges), and this pair is called \\(\\varepsilon\\)-regular, where \\(0< \\varepsilon< 1\\), if for every pair \\(W_1\\subseteq U_1\\), \\(W_2\\subseteq U_2\\) with \\(|W_1|\\geq \\varepsilon|U_1|\\) and \\(|W_2|\\geq \\varepsilon|U_2|\\) one has \\((1-\\varepsilon) d(U_1, U_2)\\leq d(W_1, W_2)\\leq (1+ \\varepsilon) d(U_1, U_2)\\). \\(d\\) and \\(\\varepsilon\\) being given it is shown that every bipartite graph \\(G= (V_1, V_2; E)\\) with \\(|V_1|=|V_2|= n\\) contains an \\(\\varepsilon\\)-regular pair \\((U_1, U_2)\\) with density \\(\\geq (1-{\\varepsilon\\over 3})d\\) and \\(|U_1|=|U_2|\\geq {n\\over 2} d^{c/\\varepsilon^2}\\), where \\(c\\) is an absolute constant. More generally \\((\\varepsilon,\\sigma)\\)-dense pairs are considered---\\(\\sigma\\) bounding the density from below---and especially for \\(\\sigma={d\\over 2}\\) bounds for the number of vertices of such pairs in \\(G\\) are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954318$B291B953-9238-41C1-A722-F1ED5E88C9D6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"84719a152f3d80016cc596ed87fee134f8b91808","datavalue":{"value":{"entity-type":"item","numeric-id":703682,"id":"Q703682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954318$40A80035-C2BF-4973-A542-11DC3BDA981A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954318$FE7C0EAB-996C-47AD-B895-5C56D812AF18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b8c13105059948515788bbaec7167056177be9e","datavalue":{"value":"1699543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954318$E59A394C-0573-45AE-8677-2864E8D5E691","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3d663c92cc86288e2df478c487898f3815f9ec0","datavalue":{"value":"regularity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954318$D6E0F178-14A7-4D1D-B644-11C9587CD233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954318$2CBCC9F9-3530-45E8-A0C8-D44A18516145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01ee01077a14e69c3c27408efccd7f448855eec","datavalue":{"value":"density","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954318$21FC4C97-9397-48A0-9FF1-E2B166DDE460","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":"Q5954318$C6BF71AF-6ACB-4FDF-8661-D6B9AF227C51","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9c1bf468a148f311d71ce2c134ff4af97f23e2","datavalue":{"value":{"entity-type":"item","numeric-id":870053,"id":"Q870053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beb0904800c211ce0da49875fb9a7e385c68dd78","datavalue":{"value":{"amount":"+0.82979345","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$C7C40934-87FF-4744-9611-89215055156C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33b24d1eecf4d99496db686494dd6671ca3ff9e3","datavalue":{"value":{"entity-type":"item","numeric-id":4589009,"id":"Q4589009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f6b845e0301a7c9328c269844a77e8db06d732e","datavalue":{"value":{"amount":"+0.8273102","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$879F5892-16D5-4544-8FB1-0459359607A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a3b96879479be07076b7638365b5f72544db209","datavalue":{"value":{"entity-type":"item","numeric-id":858679,"id":"Q858679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32e5e1c758cd6b7749d1ec9d7fb0922db8baff3f","datavalue":{"value":{"amount":"+0.81029576","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$C6B814A1-5002-4238-9529-B1869D54BB16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9e0f3d53b69ecff8d4ebe3cf9f8b2fb193495e2","datavalue":{"value":{"entity-type":"item","numeric-id":3060865,"id":"Q3060865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6412771d272f94f83e49724181cd963eebe75510","datavalue":{"value":{"amount":"+0.79551303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$0E33F3A5-10DF-4A57-B7A1-0C9F5AF22DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b33821a8022812507ea39973f8a242da777df9d8","datavalue":{"value":{"entity-type":"item","numeric-id":3608867,"id":"Q3608867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02081e1f7f7fad5408c7fcb26ea062eff9f5a63d","datavalue":{"value":{"amount":"+0.783809","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$2D6BAB90-792C-407D-896B-8CD7F9158890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0db37eb8386581be72e4f87a879cc9b037b398","datavalue":{"value":{"entity-type":"item","numeric-id":682130,"id":"Q682130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b6a15841fd458f1bb8871bf739d9b5206d1eff4","datavalue":{"value":{"amount":"+0.76767856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$5A14CDD6-BBC5-482E-88E5-922B2697DC1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ab8bd0a985aa8dce12783749c51499452445117","datavalue":{"value":{"entity-type":"item","numeric-id":5189515,"id":"Q5189515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e0d64a13a9a0018f465fc1c437a0bf16c8fd6c0","datavalue":{"value":{"amount":"+0.7671437","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$67953765-4CDE-4E2A-851D-907636091ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f50a8df2486a1abf1f44a869000816e5a768698c","datavalue":{"value":{"entity-type":"item","numeric-id":1355452,"id":"Q1355452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebc2476c0582b991d86cc5582401ce088e7baf6b","datavalue":{"value":{"amount":"+0.7641328","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$04A4043E-466F-47FE-80C2-CD52D1C7DD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3316390d574c452a262b8250f7cb70ce796b7f05","datavalue":{"value":{"entity-type":"item","numeric-id":5469145,"id":"Q5469145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"884c7d3de0782ba0eb5c7697853f5972c924d902","datavalue":{"value":{"amount":"+0.7622523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5954318$213C2543-4B3E-4A7B-A43D-A3A93DC8E9A8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c46fda4432aba8f4e3e9474ba697dfa59a3fd0fc","datavalue":{"value":"bafkreieithtv7f77n5lfgq3fdl6wmzyg4sepvdnorui62vab6jmvzbz43m","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954318$1342C636-6ACB-450B-B54D-A5DD4685E9CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5954318","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5954318"}}}}}