{"entities":{"Q6925706":{"pageid":21057292,"ns":120,"title":"Item:Q6925706","lastrevid":84131498,"modified":"2026-05-10T21:42:55Z","type":"item","id":"Q6925706","labels":{"en":{"language":"en","value":"Rainbow common graphs must be forests"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8097635"}},"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":"Q6925706$ECA48DA3-5897-4762-9070-303654B21402","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea1716834554378468ee59710db98dbaa86c78bd","datavalue":{"value":{"text":"Rainbow common graphs must be forests","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6925706$B4EBADCE-7506-46BA-9B63-B4A7C1B73863","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7b583dc1ed69016ee2ef448aef8b827e76c4af3","datavalue":{"value":"10.37236/12594","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6925706$CA544E1D-3C7F-485C-BE6C-ACEE69D6DCEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a85be6a2be6abe59dfb80e8bfb287d68d20d14b","datavalue":{"value":{"entity-type":"item","numeric-id":6399988,"id":"Q6399988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$712807B1-65C3-4AEF-A0DB-A2AD285960A4","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":"Q6925706$3E39AFCB-AE5E-4D97-8158-0646ED7B11F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e4d35ab81cabaf95bc563e9fb08a1e3335319aee","datavalue":{"value":{"time":"+2025-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6925706$7F939B54-BA7B-49F8-AF76-A13BE4456BC8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c6447482d39c2cd496160bb783e5326c870716b","datavalue":{"value":"A graph \\(H\\) is common if the number of copies of \\(H\\) in any \\(n\\) vertex graph \\(G\\) and its complement \\(\\overline{G}\\) is minimized asymptotically by the Erd\u0151s-Renyi random graph \\(G(n, 1/2)\\). This research considers the problem of maximizing the number of rainbow copies of \\(H\\), where all edges have distinct colors, instead of minimizing the number of monochromatic copies of \\(H\\). For a graph \\(H\\) and an integer \\(r \\ge |E(G)|\\), \\(H\\) is \\(r\\)-rainbow common if the maximum number of rainbow copies of \\(H\\) in an \\(r\\)-coloring of edges of the complete graph \\(K_n\\) is achieved asymptotically by coloring each edge independently with a uniform random color. Otherwise, \\(H\\) is \\(r\\)-rainbow uncommon. Settling the cycle conjecture in [\\textit{J. De Silva} et al., Australas. J. Comb. 73, Part 2, 357--371 (2019; Zbl 1411.05086)], it is proved that every graph containing a cycle is rainbow uncommon. This also extends a former result of [\\textit{P. Erd\u0151s} and \\textit{A. Hajnal}, ``On Ramsey like theorems, problems and results'', in: Combinatorics. Proceedings of the conference on combinatorial mathematics held at the Mathematical Institute, Oxford, 3--7 July, 1972. Southend-on-Sea: The Institute of Mathematics and its Applications. 123--140 (1972), \\url{https://users.renyi.hu/~p_erdos/1972-10.pdf}].","type":"string"},"datatype":"string"},"type":"statement","id":"Q6925706$1320EE1D-12BF-46E4-88C6-83D92BF2E5D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"79a8c6554e98e741fdd08e23d1518b113d533e27","datavalue":{"value":{"entity-type":"item","numeric-id":175486,"id":"Q175486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$0750A467-3919-4728-A75D-20F1D5FB0360","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6925706$74C91F4F-8DC0-49A2-9574-3999A1F4A915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6925706$E7811F77-6C35-4A1E-94CB-D9B52A25D556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6925706$DE7FAEF7-DB1B-4E6B-890B-22F501CD6D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6925706$C3038685-F091-4823-9F2D-B3989C655578","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07e8a72a215d8c9fe2af09ada8322cd28a1da872","datavalue":{"value":"8097635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6925706$B8BBF489-E9DF-4599-9DC0-D7B26AE4688F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42000534717921a0ddf9341bae79a4536ce22c61","datavalue":{"value":"rainbow common","type":"string"},"datatype":"string"},"type":"statement","id":"Q6925706$AC5A28D3-E672-4FCA-8EDD-EDCDC0231D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"558618ec18e8f22722897df7f5708ca4039f03b6","datavalue":{"value":"rainbow uncommon","type":"string"},"datatype":"string"},"type":"statement","id":"Q6925706$E1EAB4EF-2F6A-4527-8D04-BFBD01A26644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013a665df3872df6518b386ba286fc369d4eed69","datavalue":{"value":"extremal graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q6925706$0B3BEE72-2FE5-43C4-997D-3F429E2178F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8e50e8d7966d37c66b411bd473808d17082d6f3","datavalue":{"value":"probability method","type":"string"},"datatype":"string"},"type":"statement","id":"Q6925706$C7681E30-DE71-4E89-A863-12D31E1CF84A","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":"Q6925706$29A389DE-4070-4D44-A3CC-A771B42F80A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad4ff805c76c9d4e8a8522cad874b9683df97831","datavalue":{"value":{"entity-type":"item","numeric-id":2399351,"id":"Q2399351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$3112D279-855A-4236-8870-7EA12930FBCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83bb2fb7289c8cc33de66b78324b6c675be0ad49","datavalue":{"value":{"entity-type":"item","numeric-id":5377035,"id":"Q5377035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$105B6B2B-5657-456F-8946-05C0C959455B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bb537eaeed8b0c7800a3a370632c27cfb2f75a","datavalue":{"value":{"entity-type":"item","numeric-id":942107,"id":"Q942107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$694E0119-58E7-481F-809A-398A4C85643F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"496e866ff04a9807c4d7b624656b2bec9433b5d9","datavalue":{"value":{"entity-type":"item","numeric-id":1689957,"id":"Q1689957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$78260640-442D-48BA-84CE-2122923B4285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed8e4dcb8b77d6df17f554bf6f1d8f3441b0a375","datavalue":{"value":{"entity-type":"item","numeric-id":547787,"id":"Q547787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$C44C5B0F-4983-4DE2-9592-67CFC830C32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"541b793255a2075a6283a268b847326c4f5e912b","datavalue":{"value":{"entity-type":"item","numeric-id":4899293,"id":"Q4899293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$D7821EA3-B5D8-4E08-90D8-927349EEA8E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b746b3671154fd92ba5de264256b48d7331caac8","datavalue":{"value":{"entity-type":"item","numeric-id":879618,"id":"Q879618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$89835A5D-8884-442D-8315-C8E1D6438DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4163b05c117a43b724d7252a668b24fbcfbddebf","datavalue":{"value":{"entity-type":"item","numeric-id":1188766,"id":"Q1188766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$D73CD126-11DE-4773-80A7-990E0E24FEFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c13fd2b0e2637d418796b816fb16eefd6a69fe1","datavalue":{"value":{"entity-type":"item","numeric-id":2317658,"id":"Q2317658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$84E3C191-3F19-47AE-955B-999DBB231202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade0f7e2e57dbe1a00169fc17a260b947ba8bdc6","datavalue":{"value":{"entity-type":"item","numeric-id":529002,"id":"Q529002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$B432B4DF-A693-4D17-A85A-6A90B9EA18D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a31e85d0ac6606c0aa0cbe7498da937cc5f2602e","datavalue":{"value":{"entity-type":"item","numeric-id":5887506,"id":"Q5887506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6925706$5B6E34DD-9FA7-40FE-929D-0238093EB217","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rainbow common graphs must be forests","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Rainbow_common_graphs_must_be_forests"}}}}}