{"entities":{"Q1200279":{"pageid":1211028,"ns":120,"title":"Item:Q1200279","lastrevid":47116723,"modified":"2025-12-31T17:51:27Z","type":"item","id":"Q1200279","labels":{"en":{"language":"en","value":"On a bottleneck bipartition conjecture of Erd\u0151s"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 96964"}},"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":"Q1200279$256C5A4B-EAD2-4256-923B-D13B7E159709","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a08b7c25a1e6e019b1dbc400ed555b13a5067136","datavalue":{"value":{"text":"On a bottleneck bipartition conjecture of Erd\u0151s","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1200279$DC1AB25C-A916-4A1E-90A9-9F9EF83A07A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98f0f2c77324c43bd8a87ceadfa3a5d1d3232221","datavalue":{"value":"0767.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1200279$A818E5D0-FB8D-4434-8ACE-65AF14993FFF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"63b81f8843c6199ed61e086dc6b4f77bc0e835f9","datavalue":{"value":"10.1007/BF01285820","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1200279$08471C3A-4D6E-4E55-8C2C-F08ED0D7249F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ae81cb2d5ebdd030824f9f4960520397481da4a","datavalue":{"value":{"entity-type":"item","numeric-id":1200278,"id":"Q1200278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1200279$469B0889-A9B4-49F2-A608-723CC486F1D7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1200279$1926A47B-CF92-459C-B7AD-8C2B09979F65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1200279$2DBA753F-0F5E-4326-B3F5-89A37773CC3E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c535c05dfeabc069b835098a4d6bef75bc8f4535","datavalue":{"value":"This paper contains a solution to a conjecture of P. Erd\u0151s. In particular, for any graph \\(G=\\langle V,E\\rangle\\), let \\((A,\\overline A)\\) be a bipartition of the vertex set \\(F(G)\\), and define  \\[ \\gamma(G)=\\min_{(A,\\overline A)}\\max\\{e(A),e(\\overline A)\\}, \\]  where \\(e(A)\\) denotes the number of edges in the induced subgraph \\(G[A]\\). The paper mentions the computation of \\(\\gamma(G)\\) has been shown to be NP- hard. P. Erd\u0151s conjectured (1988) that \\({\\gamma(G)\\over e(G)}\\leq{1\\over 4}+o\\left[{1\\over\\sqrt{e(G)}}\\right]\\). He recognized the second moment method fails. This paper shows using a non-constructive, non- probabilistic technique that \\({\\gamma(G)\\over e(G)}\\leq{1\\over 4}\\left[ 1+\\sqrt{{2\\over e(G)}}\\right]\\). Properties of the max-cut and its relation to \\(\\gamma\\) are studied.   An extension of the problem has been done recently by the author [Graph partitions, to appear in J. Comb. Math. Comb. Comput]. Let \\((U_ 1,\\dots,U_ s)\\) be a partition of \\(V(G)\\) into \\(s\\)-classes. Define  \\[ \\gamma_ s(G)=\\min_{(U_ 1,\\dots,U_ s)}\\max\\{e(U_ 1),\\dots,e(U_ s)\\} \\]  and define the maximum \\(s\\)-cut \\(M_ s(G)\\) as  \\[ M_ s(G)=\\max_{(U_ 1,\\dots,U_ s)}\\left\\{e(G)-\\sum^ s_{i=1} e(U_ i)\\right\\}. \\]  The relation between \\(M_ s\\) and \\(\\gamma_ s\\) is studied and the following is shown.   For any graph \\(G\\), and all \\(s=2^ k\\), there is a partition of the vertex set of \\(G\\) into \\(s\\) sets \\(U_ 1,\\dots,U_ s\\), so that both, \\(e(U_ i)\\leq{e(G)\\over s^ 2}+\\sqrt{{e(G)\\over s}}\\) for \\(i=1,\\dots,s\\), and \\(\\sum^ s_{i=1} e(U_ i)\\leq {e(G)\\over s}\\). Also, Bollob\u00e1s and Scott (draft in progress) have recently shown, that for all \\(s\\), \\(\\gamma_ s(G)\\leq {2e(G)\\over s(s+1)}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1200279$623A570E-0C6E-4E13-8E21-98234BA6B2B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1200279$F77C24BA-1EB1-4E81-B097-05CDEAF9EC04","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"923b1ed775496bc8d54d64194f0b0c942bae814a","datavalue":{"value":"96964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1200279$DC8613B5-C4F9-4A83-A9FE-6E6E4856718B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86cbc34e31675eb04ae1a843b86513b14fbd867","datavalue":{"value":"conjecture of Erd\u0151s","type":"string"},"datatype":"string"},"type":"statement","id":"Q1200279$227CBBFB-C439-42BF-A843-1D48650CEE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bce2c81874566f99ebe23f22c4e5fc724fbf4c51","datavalue":{"value":"minimax","type":"string"},"datatype":"string"},"type":"statement","id":"Q1200279$26959A65-7B11-4798-930F-CAC7ADC829EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f30f01baa0dbe102ed14d61f6acd511c378aa58","datavalue":{"value":"discrepancy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1200279$FDD75221-0FCF-4BAE-AD92-7E00363DA6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26faebaf5c6873492a541ace764b53d482c99fb7","datavalue":{"value":"bipartition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1200279$3847929D-3726-4D72-AAE9-6977B05DE777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a82fb19c1a78ebdb80ce09fcea99589743cc6fd","datavalue":{"value":"max-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1200279$0D8C090F-4772-4EFD-9D2F-8438060118D3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5d9f35ef1eb804d58cb91adfa1ecbea1314c0c40","datavalue":{"value":"Q122944139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1200279$3F777995-704A-4390-9BCC-10107C288EA2","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":"Q1200279$58173F71-FF93-49B0-99FA-BE48B4367DF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b3ecf974931e2f98d11923c2936f9d6990bc1394","datavalue":{"value":"https://doi.org/10.1007/bf01285820","type":"string"},"datatype":"url"},"type":"statement","id":"Q1200279$D081D366-B50A-4CBB-B265-B2A3EBED4590","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0fc9871f2dedbb6d17c65584ac3d67c5f07409fa","datavalue":{"value":"W2013914289","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1200279$7B963F65-F0DA-4D57-A46C-6DE1F466BE64","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af90f00337f8ec0adc9460bcb0d02496689bca47","datavalue":{"value":{"entity-type":"item","numeric-id":4304346,"id":"Q4304346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bf05763dcef6493312d1f974213dd567c56fea2","datavalue":{"value":{"amount":"+0.8799874782562256","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":"Q1200279$8352F795-E4BF-4702-AF01-C45B93BAF690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6b3046e2c652be128d1f1c69eab689a4357ec13","datavalue":{"value":{"entity-type":"item","numeric-id":4840774,"id":"Q4840774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31183c92fc312f77ff4c0c6a28e1123af85e4932","datavalue":{"value":{"amount":"+0.8758629560470581","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":"Q1200279$287B9075-583F-489F-A126-6C4EA1D26F5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf7142d9a53940d5dc5c1572a56d44a788812182","datavalue":{"value":{"entity-type":"item","numeric-id":2744384,"id":"Q2744384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b32ef46f328ace8e8d8e9b80cdf6b25ff68a8fb","datavalue":{"value":{"amount":"+0.821168065071106","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":"Q1200279$3787D1F9-6C3A-48AD-A554-E39C04401428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fc980dd39ce88515fac1f39f53e5f79a7c24ba8","datavalue":{"value":{"entity-type":"item","numeric-id":4344458,"id":"Q4344458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b32ef46f328ace8e8d8e9b80cdf6b25ff68a8fb","datavalue":{"value":{"amount":"+0.821168065071106","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":"Q1200279$D79C4F29-C127-4C02-8705-DEA487200F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2328d053dd68e2ffdd3db2c6e4a0aab5dc45cfa5","datavalue":{"value":{"entity-type":"item","numeric-id":5915867,"id":"Q5915867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f57214846ba2d94e2c370f5a07fad1d103e6571c","datavalue":{"value":{"amount":"+0.8057642579078674","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":"Q1200279$BC8CAAD4-F677-4CE2-8007-865D0E840D8C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1200279","badges":[]}}}}}