{"entities":{"Q1089355":{"pageid":1100107,"ns":120,"title":"Item:Q1089355","lastrevid":49064269,"modified":"2026-01-06T13:20:22Z","type":"item","id":"Q1089355","labels":{"en":{"language":"en","value":"On universality of graphs with uniformly distributed edges"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4004220"}},"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":"Q1089355$556A55C8-A580-4B23-A946-94FEB6BCAC2B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e3b5242b46bda68ac23c5fd67e12db523b1bfb71","datavalue":{"value":{"text":"On universality of graphs with uniformly distributed edges","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1089355$54D03F81-B787-4AAA-996D-131376A56CE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6a709bb7fdc99cbcfbefaf3cf481afcd03477e4","datavalue":{"value":"0619.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$5A572711-697E-4BC9-BCDB-280B9339D712","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f232b2f33ed976d5cf42c140437b3ce1247ea850","datavalue":{"value":"10.1016/0012-365X(86)90076-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$0A69BA26-4C2F-4C1C-8B9A-D3FFC1336D25","rank":"normal"}],"P16":[{"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":"Q1089355$A87D3185-8659-436C-A491-6B45CC994A2D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089355$E02326F2-5B79-49C6-90E2-7D8C73E60B32","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1089355$1A20535E-3180-47C5-AD24-E8A32699AFC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"521e9ae2e7ed2f9be44d0a07c15e301c789308ab","datavalue":{"value":"Let \\(\\gamma\\), \\(\\delta\\), \\(\\sigma\\) be positive reals smaller than 1. Define a graph \\(G=(V,E)\\) to have property (\\(\\gamma\\),\\(\\delta\\),\\(\\sigma)\\) if the number of edges in the induced subgraph \\(<S>\\), for every \\(S\\subset V\\) with \\(| S| \\geq \\gamma | V|\\), lies in the interval \\(\\left[(\\sigma-\\delta)\\left(\\begin{matrix} | S| \\\\ 2\\end{matrix} \\right),(\\sigma +\\delta)\\left( \\begin{matrix} | S| \\\\ 2\\end{matrix} \\right)\\right]\\). The author proves the following two theorems.    (1) For every positive integer k and every \\(\\sigma\\) and \\(\\delta\\) such that \\(\\delta <\\sigma <1-\\delta\\) there exist \\(\\gamma\\) and a positive integer \\(N_ 0\\) such that every graph with at least \\(N_ 0\\) vertices, having the property (\\(\\gamma,\\delta,\\sigma)\\) contains all graphs with k vertices as induced subgraphs.    (2) For every positive integer k and for every \\(\\sigma\\) and \\(\\gamma\\), there exist a \\(\\delta\\) and a positive integer \\(N_ 1\\) such that every graph with at least \\(N_ 1\\) vertices and having the property (\\(\\gamma\\),\\(\\delta\\),\\(\\sigma)\\) contains all graphs with k vertices as induced subgraphs.    In simpler words these mean that sufficiently large graphs with sufficiently many 'uniformly distributed' edges contain all small graphs as induced subgraphs. This fails to be true for k-uniform hypergraphs with \\(k\\geq 3.\\)    The second theorem gives a 'stronger' affirmative answer to a problem posed by Erd\u0151s whether every sufficiently large graph having the property (1/2,\\(\\delta\\),1/2) contains \\(K_ k\\) as an induced subgraph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089355$8D593442-FDA4-400B-87D2-60AC0268E616","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$A4171EBF-C44F-4E2B-B7CB-DFBE1629E630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$1D185E4C-2985-4EC3-B65A-CF696B356A64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4400d479c8530601e640cf9eb914ac5b49585bc4","datavalue":{"value":"4004220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$CB65D051-AF05-4640-950D-62321E12AC5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"434abea7ee517e3f142341c3848c0140329a869a","datavalue":{"value":"epsilon regular partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089355$FD8DAC29-841D-42D5-A7E6-974B20F9ED7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e7aa9261afd174c3e2f5b7f5c7e2a299a554644","datavalue":{"value":"subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089355$74942C8B-AF17-4E47-A5A1-708E5ED259E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a621b385d2331ab32748ff7035096a56396f53d5","datavalue":{"value":"uniform hypergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089355$679B08C7-586A-4723-85B8-72EEC61C3300","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"cd0bc7a20a4fc902349d45a03456bf97a6fca404","datavalue":{"value":"Q105583518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$D0583C82-8C45-4AA6-BD1A-18AEF7C76791","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":"Q1089355$23C0DBA2-546F-41DD-8C62-B6DCA62A91AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3aefaa1fe5faab12728571c48c13e5cfc1d90a2","datavalue":{"value":{"entity-type":"item","numeric-id":1242149,"id":"Q1242149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089355$7A5750DF-C1F6-4DCE-9F29-A4A5D8BCD817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"703333cfe4b56bd5f3e74e978fd75b718cd11af1","datavalue":{"value":{"entity-type":"item","numeric-id":4056030,"id":"Q4056030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089355$F36DCAB0-D512-4BAE-B815-75E21C68B225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e953a43bd54bb7b34eeb19f7e8b742704ac8e67","datavalue":{"value":{"entity-type":"item","numeric-id":3866151,"id":"Q3866151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089355$98E9649E-844A-44DD-AD7B-638663C4A494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fb0df14392fd6a4c33fca8582ec23619b5c1add","datavalue":{"value":{"entity-type":"item","numeric-id":4071274,"id":"Q4071274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089355$CD9DF1FB-4713-4C4B-9CE1-C4948BE52B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089355$1106232E-4CD3-49C4-8A92-D6450822D240","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"440eb0956d250ea47786ca9eb9ca702a225c91c2","datavalue":{"value":"https://doi.org/10.1016/0012-365x(86)90076-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1089355$11881126-F4BD-4867-AB7B-5ECED405FFFC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9fb5c8ea19d393725cd0e81b5e48284a9b397ae","datavalue":{"value":"W1984080039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089355$643FC8EE-7706-4384-BC91-3FBEC197CB0D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51aba41ea7b1bc1bd9ed00871cb4de0ff243c0f1","datavalue":{"value":{"entity-type":"item","numeric-id":521601,"id":"Q521601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bffa1886871521e0594457bd42e3da8d3b65e6f9","datavalue":{"value":{"amount":"+0.8323161005973816","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":"Q1089355$F6408AB1-2E1C-46A1-946C-FA2B2311D082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"823103f1d34398fcdefeada787321392f2264fba","datavalue":{"value":{"entity-type":"item","numeric-id":2902906,"id":"Q2902906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bd59f4453e7d3c31bd15b5ba056047d1d06cb18","datavalue":{"value":{"amount":"+0.8131674528121948","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":"Q1089355$25874453-4689-47DC-832E-E9E27BC3469D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79cdb2ee5139980856e2ad5f19637f865f0fc528","datavalue":{"value":{"entity-type":"item","numeric-id":4190662,"id":"Q4190662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d25f2395260b3bfc54140c2bb36ea23d35b37d7a","datavalue":{"value":{"amount":"+0.8087149858474731","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":"Q1089355$2A585C47-69B5-473C-9E8F-5655C5BE825B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f6378ab4a54aba3ec58f50004431210c3ebbd66","datavalue":{"value":{"entity-type":"item","numeric-id":4631098,"id":"Q4631098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c62df9443e84fe409219c7353008fc76d8dcea1","datavalue":{"value":{"amount":"+0.8037728071212769","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":"Q1089355$AEA1DEB1-C38E-4F48-9ADF-7CE202334925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93323b75f3a0c09731dc91ab1dbd574dda7cea4a","datavalue":{"value":{"entity-type":"item","numeric-id":3061179,"id":"Q3061179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8e085a60ef02851cc8bfb3b7909ef2b88068eb0","datavalue":{"value":{"amount":"+0.8027816414833069","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":"Q1089355$0F6AA738-15FA-4143-AF62-FA9C34C1C2F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1089355","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1089355"}}}}}