{"entities":{"Q1044988":{"pageid":1046836,"ns":120,"title":"Item:Q1044988","lastrevid":66117000,"modified":"2026-04-12T07:39:50Z","type":"item","id":"Q1044988","labels":{"en":{"language":"en","value":"Random maximal independent sets and the unfriendly theater seating arrangement problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5648053"}},"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":"Q1044988$05845033-31C6-4F2C-AF37-20B5FC16029E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5eee2364a70113d21996cff2c87920ba5738dc64","datavalue":{"value":{"text":"Random maximal independent sets and the unfriendly theater seating arrangement problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1044988$CE774A69-2E14-4B6B-8065-FA3C15ACEEBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7a8442bb516fa6e1de4f8248009fc6e230a798e","datavalue":{"value":"1184.90061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1044988$35BDD113-110B-470B-BF8F-F0088C420318","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0366ca9d807050d67ac603d3f30405ebab61632a","datavalue":{"value":{"entity-type":"item","numeric-id":312656,"id":"Q312656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$85353B6F-C62C-47CC-AB6B-4D029E83D4D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca17c9763199648715858433b15ebaf2ef36218b","datavalue":{"value":{"entity-type":"item","numeric-id":215100,"id":"Q215100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$5028E9C7-3C7C-453E-BAA0-F9125FA84F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3510588941215065bc6a9d8f23e378fe2770ea1f","datavalue":{"value":{"entity-type":"item","numeric-id":215101,"id":"Q215101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$4D0C481E-2465-4ABF-9BAA-0B3F166B7BC7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$BF5CACA3-D97C-46E9-A27C-3391F41E1E01","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9d265d400060d2e7fb9c5c45adc5a5c7f5f7bbd7","datavalue":{"value":{"time":"+2009-12-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1044988$CCE99E56-3E31-4442-8F32-BA2D26BD4386","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7137f067a72c34b51f6d49988982048f5d5dc2e6","datavalue":{"value":"A problem of randomly seating people in an rectangular theater consisting of \\(m\\times n\\) seats such that each occupied seat has all 4 directly neighboring seats empty is treated. The interesting value is the expected number of occupied seats divided by seats present \\((m.n)\\).   The special case \\((m=1)\\) was solved in the year 1962, the expected value is asympotically \\((n\\to\\text{infinity})\\) \\(1/2- 1/(2e^2)\\) (=roughly \\(0.43\\)).   Two main results are shown, one is the solution of the special case \\((m=2)\\), where the expected value tends asympotically to \\(1/2- 1/(4e)\\) (=roughly \\(0.41\\)); the other is the existence of an asymptotic limit for \\(m> 2\\). The simulation results for \\(m\\) between 3 and 15 show that the limits are decreasing with \\(n\\) and for \\(n=15\\) a value of roughly 0.37 is reached -- this ``decreasing'' is stated as a conjecture, but not proven.   The solution method for the case \\(m=2\\) consists of solving simultanous recursions and I assume this method is not suitable for larger values of \\(m\\)! Nevertheless further results in this problem area are expected in the near future.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1044988$EBE87574-4C6F-47B4-A179-7B59E26CFF35","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0fde83111797a0d59e7015849b12b6c917e7b4a1","datavalue":{"value":{"entity-type":"item","numeric-id":778892,"id":"Q778892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$B39C866C-07F5-463A-A7B1-1FB591386382","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1044988$1C1074EF-E99F-4D50-A86E-66C5D5B2EFDA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9963186680f0d8a7a0bf1454d7ae38814103bc00","datavalue":{"value":"5648053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1044988$ABA8D38D-5FBC-44C7-8C71-015C43ADE332","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cd16ee5791d1e419ec8a989f06bc35bdb6647bf","datavalue":{"value":"expected value","type":"string"},"datatype":"string"},"type":"statement","id":"Q1044988$BFB4019E-9A4D-429F-AD68-523D1F2D5C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1044988$13CF0B48-04C8-4064-ADBD-A21DCC50397E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcc0e9c88f623a84d449e3796226f6e2af55dd7a","datavalue":{"value":"asymptotic limit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1044988$0ED680B9-C14C-47A9-89ED-35258D65A28C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"485f54a0549a89232924cb0abb443c2fad36af9f","datavalue":{"value":{"entity-type":"item","numeric-id":13300,"id":"Q13300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$8D0250A9-25D6-423F-B908-35969A9440CA","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":"Q1044988$FEC65741-0DE4-43E8-B9B3-2C1C768A9B95","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"78b8f5edfce80e75e83a115d5dee95e51a3ae48b","datavalue":{"value":"https://doi.org/10.1016/j.disc.2009.03.049","type":"string"},"datatype":"url"},"type":"statement","id":"Q1044988$11C1F085-0C25-42C9-82FE-45A0F30EB7C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2a99712d7a1dc908836b5cc1ff6ae896eadd7ae4","datavalue":{"value":"W2106547329","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1044988$97E4CC3C-0049-4CA0-A1A5-22F349A3B184","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"08e95261c7f9040ceee717485f5ce1b899e251cc","datavalue":{"value":{"entity-type":"item","numeric-id":1306594,"id":"Q1306594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$FFCB4BC1-1F94-4126-A5FE-81A79E09BF98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a693b09dc9e9cdd8d6e504250521ae29cdbd582","datavalue":{"value":{"entity-type":"item","numeric-id":4465661,"id":"Q4465661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$3EF94BC3-FF8A-438E-A78B-CDE70B9930F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4557c419f8822e000795f8db2ea64322f1a8482c","datavalue":{"value":{"entity-type":"item","numeric-id":4681386,"id":"Q4681386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$E81DDC5C-A38F-4868-9A4F-1DA24CBC1A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be4f85836cfeade779bb45d9f21ed63200ae5e5e","datavalue":{"value":{"entity-type":"item","numeric-id":4388978,"id":"Q4388978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$A4F33076-1B8C-4FF4-BCCD-AF0BE54E09EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23ed3cf4c3d8e896cb56ed6e77bf72829e7d71b","datavalue":{"value":{"entity-type":"item","numeric-id":1345584,"id":"Q1345584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$68A775DE-CB7C-4BA9-A427-293BAE57CCB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9f500d8bcfedd641a909557a69f68f09be263af","datavalue":{"value":{"entity-type":"item","numeric-id":4204171,"id":"Q4204171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$B3B4EF9D-086D-406A-9BD4-65A25FA8D4FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1139f0f14b827835a87190f3bded9e9bf7ea6bc","datavalue":{"value":{"entity-type":"item","numeric-id":3024026,"id":"Q3024026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$02CA3F8B-737E-4434-8751-5A6F1B7E23E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e70ab15d884118a6c94645a14b38d1bba762aff7","datavalue":{"value":{"entity-type":"item","numeric-id":1306604,"id":"Q1306604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$60EC6B0D-2116-42B0-AC3C-194A80DC03B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdff38954ff94fbe702880f7833b783360e28ca1","datavalue":{"value":{"entity-type":"item","numeric-id":3290165,"id":"Q3290165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$8B460147-3888-428F-84B9-714FCEF0E690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e2e19442f704d99dbc2813172a04f9c9d276d0","datavalue":{"value":{"entity-type":"item","numeric-id":5691080,"id":"Q5691080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$71DB093D-609B-4FB5-875D-E0620E7E516A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f7aade7e15dd4e17575a2a7ca84a0808309978","datavalue":{"value":{"entity-type":"item","numeric-id":1434674,"id":"Q1434674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1044988$BED6FCE2-1E61-4563-AD64-12DFCC28E532","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0836674ecc0fa1b3e04a1da42dac03d9af1a34d1","datavalue":{"value":"10.1016/J.DISC.2009.03.049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1044988$39962EC4-A711-4F64-B6D4-D65604E9A685","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55f46efb5d6b38c43d5a2a256b23c303e7e874de","datavalue":{"value":{"entity-type":"item","numeric-id":2804023,"id":"Q2804023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93b106494b620fbf75505017a207d77bcc2f67a0","datavalue":{"value":{"amount":"+0.861823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$D46DDC2E-1CF3-4E01-A782-F9A32C34FD42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60e179ae9f12ddaa20ea3d170d964f59c05094f6","datavalue":{"value":{"entity-type":"item","numeric-id":2407501,"id":"Q2407501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bc59769ec6ece12d0621de3cda7feb229dc4b62","datavalue":{"value":{"amount":"+0.8581355","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$7D4E122D-BF15-480A-82F3-57392ABB48F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e16f9fbe3ce50105a69051b8f43ad7d99aa179f","datavalue":{"value":{"entity-type":"item","numeric-id":4798177,"id":"Q4798177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6086680ce5a959d31ed1c90c800c045358f80aab","datavalue":{"value":{"amount":"+0.8432088","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$96C26261-364F-465E-A327-E09CB7A905E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f275910462f9602b1298ad1fa23aa9864491da3e","datavalue":{"value":{"entity-type":"item","numeric-id":1756132,"id":"Q1756132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a0c0f7618c3715d5e899699926c330815e0234e","datavalue":{"value":{"amount":"+0.8426442","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$353E3F3B-4416-4E42-BAB9-EEEF9A560603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b4e0f42e0de819319a0191e0df9654b8bd69373","datavalue":{"value":{"entity-type":"item","numeric-id":434194,"id":"Q434194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36ba481dbea775cab2498bf1764a6789c4076243","datavalue":{"value":{"amount":"+0.84215826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$10C60550-FC59-49C2-9153-681885284E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9117d74c4bb45b9ce87758a91738cd3cc025f074","datavalue":{"value":{"entity-type":"item","numeric-id":5357226,"id":"Q5357226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"761ebf225fc69e407af173bc618f51768ebb1a27","datavalue":{"value":{"amount":"+0.8397687","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$9EDFF701-94B3-492A-896F-058CCF216027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e67af38bed3c2080cbb90104289abdc78eb65eb5","datavalue":{"value":{"entity-type":"item","numeric-id":5364240,"id":"Q5364240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64ba97679514600f1cd17636612b657251f266d5","datavalue":{"value":{"amount":"+0.8382065","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$7495F17C-CA8B-488B-BE1E-26AE26391CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"476a35377a62dff554fa7daa0a2e68f361d599f1","datavalue":{"value":{"entity-type":"item","numeric-id":3599156,"id":"Q3599156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fe1b8937037a8b6b58ebfe082ee2bf800a21aa6","datavalue":{"value":{"amount":"+0.83288676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1044988$BD9DB5DE-F591-41B9-94C6-7207D9F6ACA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Random maximal independent sets and the unfriendly theater seating arrangement problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Random_maximal_independent_sets_and_the_unfriendly_theater_seating_arrangement_problem"}}}}}