{"entities":{"Q528977":{"pageid":530744,"ns":120,"title":"Item:Q528977","lastrevid":57049215,"modified":"2026-03-26T10:35:04Z","type":"item","id":"Q528977","labels":{"en":{"language":"en","value":"Large cliques in sparse random intersection graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6719975"}},"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":"Q528977$4442956D-52A4-44E7-9599-F224C2C72038","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"219370b76b52c4bce8b7046c5ba9c8fc2c95cbaa","datavalue":{"value":{"text":"Large cliques in sparse random intersection graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q528977$53A7FAD7-8EDD-4D7C-A036-685E4FBB2DF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e4eff7f8f0f6a681152743bd0d48a5d85410d1ee","datavalue":{"value":"1361.05117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$D97B8E1D-0C65-42CE-BF56-1727ECA2E959","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1fba75d8ee172b56d6e2df2636d64d60eaed8b0","datavalue":{"value":{"entity-type":"item","numeric-id":388895,"id":"Q388895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$D458B502-F3EB-4CAA-A8FA-630A37061421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"530fcb9369d189df578fdbf6e24b6f415421d58f","datavalue":{"value":{"entity-type":"item","numeric-id":388896,"id":"Q388896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$716DB6E9-0543-4078-9995-D861B1AD1278","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":"Q528977$6DF032EF-440F-4489-97BD-827499F32692","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"46a30028c10f94c4944c801c86f2de5dd37da0f3","datavalue":{"value":{"time":"+2017-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q528977$32452B54-88A6-42AA-BBC8-CE91962EA6EB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"50e262a43611985be1ee1bb1f3e116f37c650910","datavalue":{"value":"https://arxiv.org/abs/1302.4627","type":"string"},"datatype":"url"},"type":"statement","id":"Q528977$6F2E52B6-E158-40FF-B181-E24A58376505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7bd1c9dbe5317fa583f055508f621d55a0ccd7d","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p5","type":"string"},"datatype":"url"},"type":"statement","id":"Q528977$367CDF41-4D9A-4CF2-BA93-FF18DFEECB84","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b07cd27f87211ffd272d67aadfdfdc5ddb4bf73","datavalue":{"value":"Summary: An intersection graph defines an adjacency relation between subsets \\(S_1,\\dots, S_n\\) of a finite set \\(W=\\{w_1,\\dots, w_m\\}\\): the subsets \\(S_i\\) and \\(S_j\\) are adjacent if they intersect. Assuming that the subsets are drawn independently at random according to the probability distribution \\(\\mathbb{P}(S_i=A)=P(|A|){\\binom{m}{|A|}}^{-1}\\), \\(A\\subseteq W\\), where \\(P\\) is a probability on \\(\\{0, 1, \\dots, m\\}\\), we obtain the random intersection graph \\(G=G(n,m,P)\\).  We establish the asymptotic order of the clique number \\(\\omega(G)\\) of~ a sparse random intersection graph as \\(n,m\\rightarrow+\\infty\\). For \\(m = \\Theta(n)\\) we show that the maximum clique is of size  \\[ (1-\\alpha/2)^{-\\alpha/2}n^{1-\\alpha/2}(\\ln n)^{-\\alpha/2}(1+o_P(1)) \\]  in the case where the asymptotic degree distribution of \\(G\\) is a power-law with exponent \\(\\alpha \\in (1,2)\\). It is of size \\(\\frac {\\ln n} {\\ln \\ln n}(1+o_P(1))\\) if the degree distribution has bounded variance, i.e., \\(\\alpha>2\\). We construct a simple polynomial-time algorithm which finds a clique of the optimal order \\(\\omega(G) (1-o_P(1))\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$304AAB5A-BD01-469D-AE9F-552060E3BD98","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$5328C9C5-5700-4513-AB52-CE87841A10D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$4D042FD4-608D-4662-A9AE-12FD36C77D7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$F4D0CC22-307D-4E1B-BB4B-D18E82B4431A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$24D4213F-E830-4E3E-BACD-38C5125B00EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$CD8E77CD-D9F8-468F-AAE4-DD4D3B18AF63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f82567460c7721cbd6f4dc863206056ef7370b3","datavalue":{"value":"6719975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$2BB656E2-E12D-4961-BCEA-D64296913EA7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$6E5DDB2F-FAD8-4231-9F6A-4F3D4D66645F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38bca2c7224a44a28f7d1122ec4017b6a4c2ac5c","datavalue":{"value":"random intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$4BA9B096-999A-4C32-814A-545F14FFEFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$20F71618-7951-4E62-BAD1-CA9BFDC0A590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f58f8214761204715fb610e050958fbf1f486d11","datavalue":{"value":"complex network","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$FC85908B-A226-416C-A3A6-A65802D5FD7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d13767b152f704537443488cb90a76b79396b84","datavalue":{"value":"power-law","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$534A33EF-7F74-4BE4-9FA2-5B18C96C2213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9c4e650abc856b5f51d0b5123c5930fad01c53f","datavalue":{"value":"clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q528977$9AA3B0E7-EA32-4D5E-98E7-23661F47E854","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":"Q528977$6FD5D305-E4E8-4D82-B9A6-203A6AAF6D5F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"05f1166099e7ccdac142240cae0e783119977430","datavalue":{"value":{"entity-type":"item","numeric-id":3077100,"id":"Q3077100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$2699BAED-7214-426F-8293-3FAD38B685B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a07b35799ea93b75596d36219fdde17cf718f3bd","datavalue":{"value":{"entity-type":"item","numeric-id":4446871,"id":"Q4446871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$D142CDC3-56D0-4166-93B4-C9ED57BE00BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc4c6bc37d684ffae758c7d3bdab5195b61d6e6c","datavalue":{"value":{"entity-type":"item","numeric-id":3552495,"id":"Q3552495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$C1318D54-A4AF-42BB-91F6-029BFF43B912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b733c8dcf686a6065ba6a5821c6e145c1aa05162","datavalue":{"value":{"entity-type":"item","numeric-id":5189517,"id":"Q5189517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$FCCDF643-76C8-4E9A-B1C6-6AE6616FAEA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a26a5cf0078cdd3833060f2c2250238977700b41","datavalue":{"value":{"entity-type":"item","numeric-id":858491,"id":"Q858491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$0EC22404-85BD-47D4-B015-66A8BF3BEA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"991ab8cf4416b1c5fb46ca3ab102e9e39a51a305","datavalue":{"value":{"entity-type":"item","numeric-id":388897,"id":"Q388897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$92A9013A-8966-47CC-AE02-E39DB5D2F083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b32bd3b10c62a5d4baa54815c13f26acdb80adb0","datavalue":{"value":{"entity-type":"item","numeric-id":1950269,"id":"Q1950269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$4D0E2ACB-42B4-40FA-BEC1-7720F0DB26FB","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":"Q528977$2C19ABBB-8A43-4A62-AE35-1A14AE59A9C3","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":"Q528977$5FCDDB1E-8634-4362-B5B2-828C3EB3D5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a530d16e9420fdd61d460f29c588618f5e16cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5659810,"id":"Q5659810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$228C7DBD-44E7-4213-9A0A-D8B9EA6D30C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f885aa98c77a6eb678ab6c85a56fba9bada5435","datavalue":{"value":{"entity-type":"item","numeric-id":5366954,"id":"Q5366954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$C75D455F-4995-47BD-958C-174D7CCD340B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c6ed00d8027e1b18b7de582c1bb37d63a0da3fc","datavalue":{"value":{"entity-type":"item","numeric-id":3067852,"id":"Q3067852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$B8B58094-5C3E-4958-8E1E-7B8C8F222A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$C423AC89-8DE8-4AFC-9AA7-B3FC54214F35","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":"Q528977$76D6AC51-7F8B-4BCB-8480-CBFC9137CB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8be216ffca58ba5b3109ab425828c39810b0ece","datavalue":{"value":{"entity-type":"item","numeric-id":3915690,"id":"Q3915690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$7ECB396C-4562-4AA8-BC2E-10E50F52698E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b27f724ef313513f634c77777aaff9a81e9d9c8","datavalue":{"value":{"entity-type":"item","numeric-id":1942051,"id":"Q1942051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$3CACF6DA-8925-4245-BB4A-69F0F9C36E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7e876ea9827b5ef14a4e5a40a4bf150746bf43a","datavalue":{"value":{"entity-type":"item","numeric-id":5868527,"id":"Q5868527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$5E69E2C8-56B1-46B3-A5BB-3D3D67DA9994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14b5b68e795fecee578ee6f531023fb47d4d0bfa","datavalue":{"value":{"entity-type":"item","numeric-id":4226453,"id":"Q4226453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$427C477D-1E45-4EAB-A4A5-8FC7D2E5F38F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"326659ccd17e1be86a1e7c07c8a1881b0b4e27f6","datavalue":{"value":{"entity-type":"item","numeric-id":4933202,"id":"Q4933202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$B778DA97-9352-44F0-9F8F-EF5E4CC52DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003bc6c20bd1d8ced7d2a1dc42f1b9c84a55618d","datavalue":{"value":{"entity-type":"item","numeric-id":4397004,"id":"Q4397004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$395ADE3C-C7A5-48D1-B9DD-FABE9D104318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2296e4c061aa297b15b18e8b2ac7f4a7380c92ae","datavalue":{"value":{"entity-type":"item","numeric-id":5350224,"id":"Q5350224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528977$FAF47AB9-58E8-4432-A523-4EEE62B8249F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1588159c963ba939c1afec6642be541bd8b2cdc0","datavalue":{"value":"bafkreifwwvzvm6ielqqojekivghtznl337h6z5e4le4hh27hoshxzr4ziy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528977$5EDEAF6F-2E0D-4ECF-B579-533B7B404385","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a012baa0435e97caae9c8ac266425650ae0b052","datavalue":{"value":{"entity-type":"item","numeric-id":3067852,"id":"Q3067852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08015fb50e0c98396f49036738ebb916d7a80b85","datavalue":{"value":{"amount":"+0.8589259386062622","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":"Q528977$E140769D-D221-43BD-91FA-FDCEDF10A585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cd5064ef8ecc20c0e4685d6e21f95692458668a","datavalue":{"value":{"entity-type":"item","numeric-id":952443,"id":"Q952443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f1b2fc07ba713f5d0008f94c1820421ed9835e4","datavalue":{"value":{"amount":"+0.813278079032898","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":"Q528977$79C53051-E4C2-441F-AC2E-8DDF210D4270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab01ff6ef27f87c4317e7789b7b0dcd72a71610d","datavalue":{"value":{"entity-type":"item","numeric-id":1950269,"id":"Q1950269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd21da8369960ff5187ab5ac74d9f5acd99858d2","datavalue":{"value":{"amount":"+0.8070680499076843","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":"Q528977$18E64CB8-3BD4-4DBF-94D5-A5C07C7BBEEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:528977","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:528977"}}}}}