{"entities":{"Q1028807":{"pageid":1030655,"ns":120,"title":"Item:Q1028807","lastrevid":69640746,"modified":"2026-04-13T08:23:46Z","type":"item","id":"Q1028807","labels":{"en":{"language":"en","value":"Perfectly balanced partitions of smoothed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5576414"}},"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":"Q1028807$C16DE24E-F7B7-40D5-9050-2FA814992282","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8cb749b12bd667f0c9eec426591a79738363ba69","datavalue":{"value":{"text":"Perfectly balanced partitions of smoothed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1028807$9516D706-8D07-4566-8804-4E82FEA232C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f66bc85ab2b25a442c64ac6e76afb42749366728","datavalue":{"value":"1226.05225","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028807$E678A38B-7FB5-42E0-96A8-07F533DF8532","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd8d42b96f643b6dee14b749c2cac7eb296a1595","datavalue":{"value":{"entity-type":"item","numeric-id":414647,"id":"Q414647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028807$3C63E317-9133-40C9-9D28-129DC7342B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028807$FADD8205-02DF-48C7-BB6B-FEA3F528DA7D","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":"Q1028807$EF4E2264-8ED2-4CF9-9DB9-418ACD1C4B63","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b7fce5b7b399ac4add92aeecf381b606c94d340","datavalue":{"value":{"time":"+2009-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1028807$39C48CAA-71D0-465D-BA74-410E009990C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"838a950649f6149d40ccda2bf7cdb8213e06a4c2","datavalue":{"value":"https://eudml.org/doc/117498","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028807$92D70CE7-8BF6-4C94-BE49-62DB5C79923D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"57d20815f817c76bffcf1de31973acfefc0c8d2e","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n14.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028807$4C64608C-ECF5-4465-B4DD-10EB79E98200","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"24a7efcae73f19d19550f9bf9da673c201deb549","datavalue":{"value":"Summary: For a graph \\(G=(V,E)\\) of even order, a partition \\((V_1,V_2)\\) of the vertices is said to be perfectly balanced if \\(|V_1|=|V_2|\\) and the numbers of edges in the subgraphs induced by \\(V_1\\) and \\(V_2\\) are equal. For a base graph \\(H\\) define a random graph \\(G(H,p)\\) by turning every non-edge of \\(H\\) into an edge and every edge of \\(H\\) into a non-edge independently with probability \\(p\\).    We show that for any constant \\(\\epsilon\\) there is a constant \\(\\alpha\\), such that for any even \\(n\\) and a graph \\(H\\) on \\(n\\) vertices that satisfies \\(\\Delta(H)-\\delta(H) \\leq \\alpha n\\), a graph \\(G\\) distributed according to \\(G(H,p)\\), with \\({\\epsilon\\over n} \\leq p \\leq 1-\\frac{\\epsilon}{n}\\), admits a perfectly balanced partition with probability exponentially close to 1. As a direct consequence we get that for every \\(p\\), a random graph from \\(G(n,p)\\) admits a perfectly balanced partition with probability tending to 1.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028807$E37874B2-2822-4C69-951E-A4022E5D54B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028807$18F87BEC-9CA6-4961-A5F0-76AB867EDBD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028807$D29D30D8-41DB-45A7-B291-5E057B944378","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"42b34b17643a9a1adeca0f107823fd5757c221bb","datavalue":{"value":"5576414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028807$4671E650-CF6D-4FC1-8E0F-6FC7C4F435D9","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":"Q1028807$29907782-88F7-4BD6-917A-F52FA9665925","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"7599a2f9cc20dfb8b6baf847c0207e9b15a5d0dd","datavalue":{"value":"bafkreifuffka3jboaz4gaeajdaizdntxahcm2o7iqkxtp2d3ptuhnajsiq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028807$A1082FF6-FE10-4F18-918B-9481FD491760","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba0c5224f7fc145585e6dcfc95f872193d4a94a4","datavalue":{"value":{"entity-type":"item","numeric-id":3572701,"id":"Q3572701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9e0a064605efb228e4415283deeed40a5d827b3","datavalue":{"value":{"amount":"+0.7985007166862488","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":"Q1028807$C20F8C2B-AEEB-4AC5-8CE4-BE7A86090FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ac3ce2095e61ecc72ed2b28d24b538e4c1ad838","datavalue":{"value":{"entity-type":"item","numeric-id":3970898,"id":"Q3970898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b373920eab5631f3a0d9c6882f618e25d403a30","datavalue":{"value":{"amount":"+0.7832475900650024","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":"Q1028807$1798B630-AED9-4F08-A3D9-C4E35E24A303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6002c1498153a2b03378a8501df94ed6d4c8f6bb","datavalue":{"value":{"entity-type":"item","numeric-id":3195864,"id":"Q3195864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb45e261ed487f9ff7733a8f79163bb3ce7a7bb7","datavalue":{"value":{"amount":"+0.78302001953125","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":"Q1028807$1A78051A-5C28-43A7-97D7-3351FC72AA5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0ee286ad8f1fde6fef20931c61a27693aa672be","datavalue":{"value":{"entity-type":"item","numeric-id":5190331,"id":"Q5190331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66cc10d78d0ebb868392a1411b1618a415182031","datavalue":{"value":{"amount":"+0.7785215377807617","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":"Q1028807$6D05E957-EE90-48FE-B9D8-292B4B27CFFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"989f36e79eb51698caae5c0529b39b15f835a885","datavalue":{"value":{"entity-type":"item","numeric-id":2875685,"id":"Q2875685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a797f57f54d14486da89fd93157c90e06068c04","datavalue":{"value":{"amount":"+0.7779676914215088","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":"Q1028807$7B4CEDAE-18B9-4B59-9617-C88DDBA3B50F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Perfectly balanced partitions of smoothed graphs","badges":[]}}}}}