{"entities":{"Q2338615":{"pageid":2349358,"ns":120,"title":"Item:Q2338615","lastrevid":57858153,"modified":"2026-04-02T20:13:32Z","type":"item","id":"Q2338615","labels":{"en":{"language":"en","value":"Density of monochromatic infinite subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7134835"}},"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":"Q2338615$BC106FD3-4671-4D97-B618-CEB92D40B6E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ec4046c83377f657c343ae466a8bf9bd753347cd","datavalue":{"value":{"text":"Density of monochromatic infinite subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2338615$A8AEAAA8-993B-4495-A103-019141EEB731","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9593af9b5edde420d63dc7027c110eadbf545973","datavalue":{"value":"1438.05173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$BF3768FD-CE92-42EA-A9AA-BFDA8B11A400","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f988a0b91db170aa38adba2cb9825a10a2dfd1a7","datavalue":{"value":{"entity-type":"item","numeric-id":345112,"id":"Q345112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2338615$D4E1A9F4-F982-4899-9CB4-FA8BBED449A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d5860a089d2a1ad55a03a343948e64d4c2ce135","datavalue":{"value":{"entity-type":"item","numeric-id":436629,"id":"Q436629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2338615$D9554F27-54C4-4683-92B8-FD34466AEF6A","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":"Q2338615$2DA87FF5-0923-4706-9161-BE02AC47CFEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df8a8a76ae09508c8444c01bbacb33e3edfbee9a","datavalue":{"value":{"time":"+2019-11-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2338615$66B606A4-146F-4BE5-9ED5-D123BF429170","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dc2c53b03de3a618c1a043ffeed11ab789590878","datavalue":{"value":"https://arxiv.org/abs/1611.05423","type":"string"},"datatype":"url"},"type":"statement","id":"Q2338615$04015515-1620-48D9-AA95-A59FBD114E23","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c3ed5363898ee443092a3ecffd7c124d9079536","datavalue":{"value":"The paper under review is concerned with complete infinite graphs with vertex set the natural numbers, where we assign a colour to each edge of the graph, and seek to find monochromatic (infinite) paths in this graph which have large density. We use two notions of density of a subset \\(A\\subseteq \\mathbb{N}=V(G)\\): the upper density is given by \\(\\overline{d}(A)=\\limsup_{n\\rightarrow\\infty}\\frac{\\vert A\\cap \\{1,2,\\ldots, n\\}\\vert}{n}\\). We also consider the strong upper density; given an infinite sequence \\(A=a_{1},a_{2},\\ldots \\) with \\(A\\subseteq \\mathbb{N}\\), we define \\(\\overline{d}_{s}(A)=\\limsup_{n\\rightarrow\\infty}f(n)/n\\), where \\(f(n)=\\sup\\{m:\\{a_{1},a_{2},\\ldots ,a_{m}\\}\\subseteq \\{1,2,\\ldots, n\\}\\}\\). Clearly \\(\\overline{d}_{s}(A)\\leq \\overline{d}(A)\\) as the left-hand side only counts the density of unbroken initial segments of a path whereas the latter allows ``re-entry''.\\par The first main result of this nice paper (Theorem 1.6) is that in every 2-colouring of the edges of the complete graph on \\(\\mathbb{N}\\), \\(K_{\\mathbb{N}}\\), there is a monochromatic path \\(P\\) with \\(\\overline{d}(P)\\geq 3/4\\). This improves an earlier result from \\textit{P. Erd\u0151s} and \\textit{F. Galvin} [Discrete Mathematics 113, 59--70 (1993; Zbl 0787.05071)] who proved a weaker version with \\(3/4\\) replaced by \\(2/3\\). The best known upper bound on the density, again from the earlier paper by Erd\u0151s and Galvin [loc. cit.], is 8/9 and the authors conjecture (Conjecture 8.1) that \\(8/9\\) is the correct answer. \\par The second main result is that in every 2-colouring of the edges of \\(K_{\\mathbb{N}}\\) there exists a monochromatic path with \\(\\overline{d}_{s}(P)\\geq 2/3\\). As Erd\u0151s and Galvin [loc. cit.] had proved in their earlier paper that there is a 2-colouring of the edges of \\(K_{\\mathbb{N}}\\) in which every monochromatic path has \\(\\overline{d}_{s}(P)\\geq 2/3\\) this completely settles the question for strong density of a monochromatic path in \\(K_{\\mathbb{N}}\\) with two colours. \\par The authors also make remarks about cases with more colours, directed graphs and connected components more general than paths. A large range of techniques are used in the proofs. Several open problems are listed at the end of the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2338615$578B060D-F40C-4D06-B49B-C1EE1524FAA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$21C4F442-1973-41C4-A875-8BE830815D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$35AADF2B-8624-4BB9-8BEA-701DB5DBD625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$A8991F03-D5C2-4351-9ABE-F13860454E35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$43811BCF-5728-41AD-A722-559B538CB0EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5b6c9fdd877a1d3bbf80c83d0bd4ea80cab10709","datavalue":{"value":"7134835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$EF572DF4-D981-4723-A245-0F60056A5E8E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7146c2819fbeedb702f7b725ef135774812891af","datavalue":{"value":"infinite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2338615$9BAD158C-6A98-4DE5-8DBF-4CE56ADC32C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abfb9f1d3465fe07356a59f9ac724c7697f981ad","datavalue":{"value":"coloured graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2338615$E54BA608-63D7-43C2-9C52-2C6C211A9B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ebc22d8187ea672fec2c0fc855212abe29ca422","datavalue":{"value":"longest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2338615$DA729286-3D56-4D75-BBCC-9203ABB859C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01ee01077a14e69c3c27408efccd7f448855eec","datavalue":{"value":"density","type":"string"},"datatype":"string"},"type":"statement","id":"Q2338615$8CFC3EAA-D195-4B03-8AAA-72D0053A51F7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2338615$55ADCA89-BDA5-4F24-9DD3-245E776C7FD0","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":"Q2338615$1CD3A530-7776-4723-92A9-C8E28857DEC2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d6b667d2c39c6a9e21ee521a911ba36c45d7c43","datavalue":{"value":"W2963526460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$1D0E65D9-1B26-4BA5-8067-64A8F8530D2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d08422c359f68e0d124d07b2f60df1fd9b577709","datavalue":{"value":"10.1007/S00493-018-3724-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2338615$FE779E39-7006-4862-B3DE-A429BBE5DFB2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25103c4f78724938d115336506757c5b250cc2c2","datavalue":{"value":{"entity-type":"item","numeric-id":1627204,"id":"Q1627204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21ac7b59b53466327791a45d4eaa97c0a4f58927","datavalue":{"value":{"amount":"+0.9479186534881592","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":"Q2338615$03F6DB22-3B00-496A-8845-64504C165318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20cc57c4b9ede55b991d4b08bba3ea3a74e01a66","datavalue":{"value":{"entity-type":"item","numeric-id":5126750,"id":"Q5126750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59437b3b881f924b642233b3b723922ccacbed43","datavalue":{"value":{"amount":"+0.9324815273284912","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":"Q2338615$01E95989-656B-4A4B-80FD-C64F4BB86C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4368de4b31184fb2834bcee5d216c5805934e07a","datavalue":{"value":{"entity-type":"item","numeric-id":6100872,"id":"Q6100872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e502e6cecc7b8f2950192415de14ad9a8a34d8a","datavalue":{"value":{"amount":"+0.9323582053184508","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":"Q2338615$6AAB72E8-26CB-4797-83E4-FE0E5F11B374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4efc89cb0fa3268aaaf4e37724b906287ad24ddd","datavalue":{"value":{"entity-type":"item","numeric-id":2366010,"id":"Q2366010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14d30f9a93c963d92a8320596b05bce5c89dd335","datavalue":{"value":{"amount":"+0.9280890822410583","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":"Q2338615$A3297363-21B6-4FAA-B3E3-B99269CE3607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"345f98b74e16a7a8d7e6eeb2b09dec1712c6ba2f","datavalue":{"value":{"entity-type":"item","numeric-id":1783629,"id":"Q1783629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18d1eeea58490c97b803b14e9c906a0572a319f7","datavalue":{"value":{"amount":"+0.9261184930801392","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":"Q2338615$8134704B-9CA2-49CB-997B-1F9C8A70AF8F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2338615","badges":[]}}}}}