{"entities":{"Q650910":{"pageid":652759,"ns":120,"title":"Item:Q650910","lastrevid":63320136,"modified":"2026-04-11T12:04:48Z","type":"item","id":"Q650910","labels":{"en":{"language":"en","value":"On the independence number and Hamiltonicity of uniform random intersection graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5987001"}},"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":"Q650910$05936EFC-1C8A-4B8B-8C06-9C9F8E95FA4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"801a48eaa6de8cb1a25b31a19682e0b9ab8784e6","datavalue":{"value":{"text":"On the independence number and Hamiltonicity of uniform random intersection graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q650910$8258BFC7-0EEF-46BD-82EF-C3EE23B5B747","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"703c2f9764077f3e784ba6418630a14b88f3888d","datavalue":{"value":"1233.05186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$E99299EF-E2A1-48A4-8E0F-B84DBF754FAA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8112a4884ac488e222bb031fe5d75202a7b6dcb","datavalue":{"value":{"entity-type":"item","numeric-id":389952,"id":"Q389952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$4CC5FCDB-5B4D-443F-9AB1-B38B38857338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e89b82472d012661ff5b9a16b10f1c4eff7b4eef","datavalue":{"value":{"entity-type":"item","numeric-id":518675,"id":"Q518675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$E2D4AA6A-224B-4AB3-83E3-A901021BB045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0cd9301f7be4e3f0c2ba94f932efa5f23f6275f","datavalue":{"value":{"entity-type":"item","numeric-id":518676,"id":"Q518676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$0DB28BDD-47E9-4014-9D7C-CBE677EAF7BE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$CEDA9727-321A-4C80-B6D7-44ABD428C2B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e38c6f1e03c0365fe5e243370e140f97607764e2","datavalue":{"value":{"time":"+2011-12-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":"Q650910$E9244E17-A224-4F66-ABA4-91C65B1F7CBE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cba75738703c97a9070f9783cae99abb302d9d1c","datavalue":{"value":"This paper studies the independence number of random intersection graphs \\(G_{n,m,\\lambda}\\) on \\(n\\) labelled vertices where each vertex takes from an \\(m\\)-element set \\(S\\) one of the \\({m\\choose \\lambda}\\) subsets of order \\(\\lambda\\), all such choices being equally likely and all vertices choosing independently. We then say that two vertices are adjacent if and only if their sets intersect.  The main results of the paper under review concern existence of Hamilton cycles and independence numbers in these graphs. The first result is that if \\(\\lambda\\geq 2\\) and, for some (small) constant \\(\\epsilon>0\\), \\(n\\geq (1+\\epsilon){m\\choose \\lambda}\\log({m\\choose \\lambda})\\), then \\textbf{whp} (i.e., with probability tending to 1 as \\(n\\rightarrow\\infty\\)) there is a Hamilton cycle. (For \\(\\lambda=1\\) and \\(m\\geq 2\\) the graph is \\textbf{whp} disconnected). The argument is a coupon-collecting one. For further progress since the paper under review, see [\\textit{M. Blozelnis} and \\textit{I. Radavi\u010dius}, ``A note on hamiltonicity of uniform random intersection graphs'', Lith. Math. J. 51, No.\\,2, 155--161 (2011; Zbl 1226.05226)].  The paper also studies the size of independent sets. If \\(m=\\lfloor n^{\\alpha}\\rfloor\\) with \\(\\alpha<1\\) and \\(\\lambda=O(m^{1/4})\\), then for a certain number \\(c_{0}=c_{0}(\\alpha,m,\\lambda)\\) (a solution of an equation involving these parameters) we have that \\textbf{whp} the largest independent set has order not more than \\((1+\\epsilon)m/(c_{0}\\lambda)\\). Further, an application of the second moment method shows that we get close to this bound.  The authors finally show that in \\(G_{n,m,p}\\), where, instead of choosing a \\(\\lambda\\)-element subset of \\(m\\) uniformly at random, each element of \\(S\\) is in the set of a given vertex with probability \\(p\\) independently of all other vertices, the independence number is \\textbf{whp} at most \\((2+o(1))\\log(n)/(mp^{2})\\) provided \\(p(n)\\) grows faster than \\(\\log(n)/n\\) and is \\(o(\\sqrt{\\log(n)/m})\\) which in turn is \\(o(1)\\). Again, a second moment method argument allows us to get close to this upper bound, under slightly more restrictive conditions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q650910$D38E18F0-84BB-4816-84FC-F1D5105300B1","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":"Q650910$E961EF94-931F-4AF6-869E-75EB3BD6C391","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$F67B9124-828A-4758-A6EF-6BDE0A22091A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$F0EEB5AB-1939-459E-AB29-6C23D26DDC52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$D640A164-F902-4758-8F6C-AF989210BB78","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c9784d26fb234b0901e304b2b952718504095c2","datavalue":{"value":"5987001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$3395D259-A27D-4099-BE32-463197C7DE68","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q650910$5E206AE0-EA64-41E8-BF50-F0F7A55F68D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q650910$093AC785-2592-40DA-9B27-863A796B7EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q650910$648D5D37-215E-4C29-A0B2-B256B4B2FDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q650910$D6C48441-AA45-4077-A80C-91E6710E9D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06cae65688d3385aec26afb1fc9e9a3ede5455e6","datavalue":{"value":"probabilistic methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q650910$69205725-F821-4D14-8156-42E4092EA4A0","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":"Q650910$0F02CB3D-033A-4BAC-AA89-B39B60B3A993","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"22ed19e5d9b664b9fe63cbcc2fb6162d684b29f9","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.09.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q650910$019697C3-3BCB-4857-81E2-09CBDE14C949","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d8fa8adda64f0d44b1c30504f67c24f826effd6","datavalue":{"value":"W2014672313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$7E661F53-2303-4A3C-99EE-FAC556EB961F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9208528a9398d42022a83d3910fdcc8477ab6c6","datavalue":{"value":{"entity-type":"item","numeric-id":2784326,"id":"Q2784326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$FF46E6B7-B981-4551-A04C-ABADE09E9873","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80446eb4082c94d6c4451a96b245ff2ceec3ee51","datavalue":{"value":{"entity-type":"item","numeric-id":1044989,"id":"Q1044989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$7AD98E3B-9693-47D9-AC80-76EECD1D2BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c534fa6e182361abf9b2a40adbf5d398f8c9ef3a","datavalue":{"value":{"entity-type":"item","numeric-id":946799,"id":"Q946799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$C087E050-D36F-4A90-AE81-C2610E70B5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e193c255aa93d51c68d002eb73b91311978dd3b","datavalue":{"value":{"entity-type":"item","numeric-id":3088119,"id":"Q3088119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$03C7E056-FD06-411C-A7DC-4BA416642896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5e2ae03db3f5386c6f29c3d795bb07d443bd5d","datavalue":{"value":{"entity-type":"item","numeric-id":3644944,"id":"Q3644944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$F9C49028-0F47-4F78-89DE-4FD1F6220CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fecb60d0293a366a76b77145f9c5565a9e981ceb","datavalue":{"value":{"entity-type":"item","numeric-id":5716819,"id":"Q5716819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$FAA803DF-9913-48BD-8979-7DB6277DFC98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed9d34a6aed6f4131de1fde7d4217ad01d9a3ffe","datavalue":{"value":{"entity-type":"item","numeric-id":4243076,"id":"Q4243076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$97849A08-61F7-4675-9500-1465527909E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c73bcc6fc814d1a9a3c665e257596f500445642e","datavalue":{"value":{"entity-type":"item","numeric-id":5466535,"id":"Q5466535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$C3D3F0EB-21E1-40D5-90A2-1124D62C180D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a513f281a29e93dd9cacae932002d36e371b8c56","datavalue":{"value":{"entity-type":"item","numeric-id":3525554,"id":"Q3525554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$591503CA-31A6-4173-A545-67DD0D7F8C4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d275c7cc3c48b8dcc757e314aa0a79a0fa9e8ce1","datavalue":{"value":{"entity-type":"item","numeric-id":5897882,"id":"Q5897882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$3A809EF4-71AD-4EAA-B7E2-71512698A8D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18e4d260436afb3e9e38e12dcc56579492065db8","datavalue":{"value":{"entity-type":"item","numeric-id":4736773,"id":"Q4736773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650910$2E635306-EC96-4FFA-BB6E-2B26CFECFA88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38a8d6fb7a187334fece1dbb3968cc2416d2081c","datavalue":{"value":"10.1016/J.TCS.2011.09.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650910$70BE2400-4F12-4A13-AF9D-820464694ED5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"794d0f88a48a7e438f3cf581d9d2a5f120a28a26","datavalue":{"value":{"entity-type":"item","numeric-id":647151,"id":"Q647151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76c78978786c645d3437191b1827f7527838f622","datavalue":{"value":{"amount":"+0.8895713686943054","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":"Q650910$55534E8D-53D9-4211-A446-7760D024CB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c24096aee27ed0fb579fe10ff1552736ee2a21","datavalue":{"value":{"entity-type":"item","numeric-id":5716819,"id":"Q5716819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17febf386388c91100ce5efd02af68aa68b3e50c","datavalue":{"value":{"amount":"+0.8737127184867859","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":"Q650910$955B70DC-4E6A-4F17-B3CF-1863F4625A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18b11a45d4a89114ad1a400afe80e86715dc94de","datavalue":{"value":{"entity-type":"item","numeric-id":2810028,"id":"Q2810028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"702a861c208df6b1cdc73273c517a0ebb221411b","datavalue":{"value":{"amount":"+0.8675324320793152","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":"Q650910$9A238C45-A297-468B-B980-99E6CE3CB6C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"438626235db85a32e4b64b4c8f3ad79fe2d3cdc6","datavalue":{"value":{"entity-type":"item","numeric-id":708225,"id":"Q708225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec8b7c71b3619aa36d7df3fd9ed622d5f998f076","datavalue":{"value":{"amount":"+0.8431290984153748","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":"Q650910$953AABE2-046C-4CB9-8D80-611863200AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0170c40943f8fd68ed5b39860fa8f9ada363a25","datavalue":{"value":{"entity-type":"item","numeric-id":3098045,"id":"Q3098045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bd88dc07eb61b56e47bc6c5dca242b397ca65cf","datavalue":{"value":{"amount":"+0.8327750563621521","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":"Q650910$7211D4AB-A7B7-43CE-9A4A-5EEB9155F9E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the independence number and Hamiltonicity of uniform random intersection graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_independence_number_and_Hamiltonicity_of_uniform_random_intersection_graphs"}}}}}