{"entities":{"Q1978060":{"pageid":1988802,"ns":120,"title":"Item:Q1978060","lastrevid":46901268,"modified":"2025-12-25T19:57:16Z","type":"item","id":"Q1978060","labels":{"en":{"language":"en","value":"A note on the non-colorability threshold of a random graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1456994"}},"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":"Q1978060$F31B7357-6D0E-49D2-930B-78C7E36F4586","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa7f498e513c282a6775fb7bfb1008d761bd7b0c","datavalue":{"value":{"text":"A note on the non-colorability threshold of a random graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1978060$1D4CB45A-D23B-4FE5-91A2-7BA61A8A020F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed598c7963330a6a25f6324d1de9816b132cb752","datavalue":{"value":"0939.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978060$2D2FD2AE-E14F-423E-8AF3-807ACC744E4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3114a9e7c18fd9d37962020c44023cd148b8085d","datavalue":{"value":{"entity-type":"item","numeric-id":215098,"id":"Q215098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978060$6B43E19A-5AC1-4411-9270-65F2F1379108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"470ab19ea59c903ef70cce34096820e8d1297da8","datavalue":{"value":{"entity-type":"item","numeric-id":215099,"id":"Q215099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978060$83907712-3E05-47BF-BCDE-9E5C91E7D39B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b2c08274843d792a282cbffaf38d6d5529415ecf","datavalue":{"value":{"entity-type":"item","numeric-id":389950,"id":"Q389950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1978060$3F685CA1-C8F8-4507-A17A-350E356B8695","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":"Q1978060$F3FF19F7-9DF5-4B20-8E4B-ACE8BF727CDF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f824e8df8660a01a22c6ea772f84f035aa08b14a","datavalue":{"value":{"time":"+2000-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1978060$0559F401-7576-4698-B7D2-DB7D6B14F70D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bda02f3ccbdaa39669fbafcfbeae5240dbaa370a","datavalue":{"value":"https://eudml.org/doc/120357","type":"string"},"datatype":"url"},"type":"statement","id":"Q1978060$E6758F95-CCAD-431C-880A-66FE77258455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4872c37291c770fb6fa9a0b10e6322f1ebf49fc","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r29.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1978060$4F68F5A9-BB54-4BF5-8356-19336E9CD760","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d33931dfaf59d3ff2e575ba3fd726f0b769f9328","datavalue":{"value":"Summary: In this paper we consider the problem of establishing a value \\(r_0\\) such that almost all random graphs with \\(n\\) vertices and \\(rn\\) edges, \\(r > r_0\\), are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins. Using the sharp estimates obtained by \\textit{A. Kamath}, \\textit{R. Motwani}, \\textit{K. Palem}, and \\textit{P. Spirakis} [Random Struct. Algorithms 7, No. 1, 59-80 (1995; Zbl 0834.68051)] of the probability that no bin is empty after the random placement of the balls and exploiting the relationship between the placement of balls and the rigid legal colorings, we improve the value \\(r_0 = 2.522\\) previously obtained by \\textit{D. Achlioptas} and \\textit{M. Molloy} [Electron. J. Comb. 6, No. 1, Research paper 29, 9p. (1999; Zbl 0919.05056)] to \\(r_0 = 2.495\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978060$9CD3A2F7-101D-436F-AAC0-78071C9F8744","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978060$8861CAAE-2067-4B28-AC8B-C820B436527A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978060$51A8D7F2-5C2E-40FC-BD30-F34A5A2BEFBF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b1993e84c493a473b15a622bb3235d71dc1e1d9","datavalue":{"value":"1456994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978060$BB00400A-9C0A-40F3-B116-B0F50F11AC25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"358fcec8d8d5a27a0e19fc52e20cfa58dcfd178c","datavalue":{"value":"non-colorability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978060$719BACE1-712C-43ED-9F04-A05597155CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978060$CB629B3D-5ADC-4576-8124-0FE6F32539E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"245bb46b54951018ca725c73286f7f519e3b12ac","datavalue":{"value":"colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978060$2380E34E-CBCA-4C2D-9D42-B2747826EA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3743528dc6131056fb666aabe2500b92c714914","datavalue":{"value":"occupancy problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1978060$D39DE5BD-23C1-4E47-8C9D-A9A7080F72E2","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":"Q1978060$5F7E6D8D-4CF6-4864-A671-ECB329C448B5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5dcbff21a328b5bcbe36986d56a955339d342438","datavalue":{"value":"bafkreibg7p4uhgte6w5vsbr2u22qhe2hdstlgp7w3hrtrtpbdm7lik3d4u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1978060$6A446F8D-9077-45B6-8617-4D053A7F6B08","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa0c5a8c09d0be4073cdce049f44d1c8de72545f","datavalue":{"value":{"entity-type":"item","numeric-id":4483917,"id":"Q4483917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"472a5961f5f4897b83e7dcf3fc64bfd56028967b","datavalue":{"value":{"amount":"+0.8625901937484741","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":"Q1978060$59957DC6-FF66-4D6D-B298-E923FBA52C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40ea9ed68f1425e7d4cc11c6774b6a2b726851fc","datavalue":{"value":{"entity-type":"item","numeric-id":1298442,"id":"Q1298442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd6d62b2588edcffce29116f21847741c092d1d2","datavalue":{"value":{"amount":"+0.8514914512634277","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":"Q1978060$B62C191E-9D0D-4364-AC72-D22FD70FAFA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45cc5aa5564268e6cf7af10dbc0a54b9a8602f05","datavalue":{"value":{"entity-type":"item","numeric-id":4705349,"id":"Q4705349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc759eaf119332622ef21b782602497f5c47820e","datavalue":{"value":{"amount":"+0.8222681879997253","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":"Q1978060$C44CC424-CC0F-4815-A749-B275F18230B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b9dd57f1a289bbc50f83ffb135c230a11171ea3","datavalue":{"value":{"entity-type":"item","numeric-id":293171,"id":"Q293171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"485fbd3aaf02f820264617cea52d2b7728aff09c","datavalue":{"value":{"amount":"+0.8140468597412109","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":"Q1978060$EA1231C0-BC92-49A1-90A5-127DCCF17A1E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1978060","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1978060"}}}}}