{"entities":{"Q2334869":{"pageid":2345612,"ns":120,"title":"Item:Q2334869","lastrevid":57865545,"modified":"2026-04-02T20:58:40Z","type":"item","id":"Q2334869","labels":{"en":{"language":"en","value":"Induced subgraphs of hypercubes and a proof of the sensitivity conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7128144"}},"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":"Q2334869$520CA38F-72E4-4326-BD45-A3EFB17D782E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5dcbb054209a7ad92bcdc15cf9e74b1507cbd9e","datavalue":{"value":{"text":"Induced subgraphs of hypercubes and a proof of the sensitivity conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2334869$76E83433-775B-4C62-A4FE-594953DBAF48","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3bb94cff5de5246f3f05ffff7809e70d5c7c5841","datavalue":{"value":"1427.05116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$EBB91896-966B-4618-9892-E4315B485CE5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b7cc925a2adff2795d8245c6397eac2206eb76c","datavalue":{"value":{"entity-type":"item","numeric-id":405285,"id":"Q405285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$37FF3517-AAD6-4432-A9A0-1566F72836C3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$F3591FDD-7BF1-443B-B486-7220D5A0499C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"85b8b3f0adb54ca4d37615507bf5cd1db9cf6ef8","datavalue":{"value":{"time":"+2019-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2334869$E38A9371-09BF-459F-BF24-C29912131738","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a265840037da2404860c2b34da2176b374acf472","datavalue":{"value":"https://arxiv.org/abs/1907.00847","type":"string"},"datatype":"url"},"type":"statement","id":"Q2334869$92F57CD8-28FC-4EB8-9BCD-59B84667A26D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"adaefb64a74bbba04977be2c12348d44997515d4","datavalue":{"value":"The \\(n\\)-dimensional hypercube \\(Q^{n}\\) is the graph with vertex set being the vectors in \\(\\{0, 1\\}^{n}\\) where two vectors are connected by an edge when they differ in exactly one coordinate. Let \\(\\Delta(G)\\) denote the maximum degree of a vertex in \\(G\\). This paper proves the following main result.  Theorem 1. Given an integer \\(n \\geq 1\\), let \\(H\\) be an arbitrary induced subgraph of \\(Q_{n}\\) on \\((2^{n-1} + 1)\\) vertices. Then \\(\\Delta(H) \\geq \\sqrt{n}\\) and this inequality is tight when \\(n\\) is a perfect square.  Through a sequence of equivalences, this result proves the sensitivity conjecture, stated below as a theorem. Given a vector \\(x \\in \\{0, 1\\}^{n}\\) and a set of indices \\(S\\), let \\(x^{S}\\) be the vector obtained from \\(x\\) be flipping the bits of \\(x\\) in the positions corresponding to indices in \\(S\\). The local sensitivity of a Boolean function \\(f: \\{0, 1\\}^{n} \\rightarrow \\{0, 1\\}\\), denoted by \\(\\operatorname{s}(f, x)\\), is the minimum number of indices \\(i\\) such that \\(f(x) \\neq f(x^{\\{i\\}})\\). The sensitivity of \\(f\\), denoted by \\(\\operatorname{s}(f)\\), is then defined as \\(\\max_{x} \\operatorname{s}(f, x)\\). Similarly, the local block sensitivity \\(\\operatorname{bs}(f, x)\\) is the maximum number of disjoint blocks \\(B_{1}, \\dots, B_{k}\\) (subsets of \\([n]\\)) such that for each \\(B_{i}\\), \\(f(x) \\neq f(x^{B_{i}})\\) and the block sensitivity of \\(f\\), \\(\\operatorname{bs}(f)\\), is \\(\\max_{x} \\operatorname{bs}(f, x)\\).  Theorem 2 (sensitivity conjecture). For every Boolean function \\(f\\), \\[ \\operatorname{bs}(f) \\leq \\operatorname{s}(f)^{4}. \\]  The main result is proven by a sequence of lemmas, including Cauchy's interlace theorem, which describe the eigenvalues of symmetric square matrices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2334869$40FC9A2F-476C-4548-B98F-0B13CAE7ADE8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"439d970fbbaf9f34e47b79ca6b5b8be34dfa4f61","datavalue":{"value":{"entity-type":"item","numeric-id":293605,"id":"Q293605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$B38C595F-7575-4E56-BCA3-1CD79BB391D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$362A1B23-767A-43DA-82D6-0FF0DE7E8DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$2C46B6F7-FCEA-4F36-B287-3CE479E23FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$FE35654E-F669-4845-B393-25E02E50E140","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac11d1636029e15e84caeb4c8b1c85987ebff46a","datavalue":{"value":"7128144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$310BFFEE-FBC5-42B8-9B3F-D9CCB1F9CC11","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87dbfaba0f8b891179fd14ab6123ae5895ff3fb3","datavalue":{"value":"sensitivity conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2334869$DF60A5F8-AB21-46DA-ABE1-15D03D96DA14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2334869$1B5EA830-72BC-47C3-9425-9A8C3FC672B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q2334869$5B189E3D-9884-48AC-8504-91EBBFF63E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70dc85fcc07cd5b7924230f014634c1228af5736","datavalue":{"value":"eigenvalue interlacing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2334869$E1FC0B52-B61F-4B73-9FC4-B45D4A039F49","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":"Q2334869$1B59D277-85C8-4ADF-8959-782E6C42994A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"500153d8ca836189dde5cd6bdf976b3a4f759491","datavalue":{"value":"Q87647546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$3750DC19-D511-427A-97A0-E118787B2CF7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b91d770eb5eee7f9435a0b21de148df0892d8530","datavalue":{"value":"W2982703414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$22DB19C7-B42E-4B97-B565-2510DE0B6080","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9872d1e5b694c452e067c737826bed9fab5fdb53","datavalue":{"value":{"entity-type":"item","numeric-id":1853508,"id":"Q1853508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$C63AF3EF-F18C-4539-A401-D3538A8DA633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a369e00d222394499fbeac6ef2d4a8f0d1db95e1","datavalue":{"value":{"entity-type":"item","numeric-id":1107541,"id":"Q1107541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$FCEF3B0C-0976-426E-965E-AE2EAB1536AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6346de8cbf8b9a5d2644300692d94de4347098d","datavalue":{"value":{"entity-type":"item","numeric-id":5703685,"id":"Q5703685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$F852C58B-B6C7-439C-8DBB-20FF8F650B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aaee1f764fb70b09f7a4bef8df7b1bb11e0d712c","datavalue":{"value":{"entity-type":"item","numeric-id":2989036,"id":"Q2989036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$B50B804A-4540-46E2-BBBA-C0E69E034135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c795427d734dae084ad25ee22194b358125361e2","datavalue":{"value":{"entity-type":"item","numeric-id":2800553,"id":"Q2800553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$BBDD5ACC-FC97-4B96-9FA4-D543935EC199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56d146069b2b6ab351534134e8171629a27d48e7","datavalue":{"value":{"entity-type":"item","numeric-id":5368747,"id":"Q5368747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$1BFFB448-88DF-49B6-8C4E-3DA42B117B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6eb1fdd303650b9459c1ff97c8f380110b4512a","datavalue":{"value":{"entity-type":"item","numeric-id":1194759,"id":"Q1194759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$9956B0E2-44D6-4030-ADA8-E2A0F8DFE937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72d503ddcdeb79b92ba064d615eeb6838f8bf6ee","datavalue":{"value":{"entity-type":"item","numeric-id":1887146,"id":"Q1887146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$55A1ADD6-FE44-4C17-927F-4356DC20FA00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c78c20459dff182618761f69f8bfcf22d8fe9d","datavalue":{"value":{"entity-type":"item","numeric-id":1346612,"id":"Q1346612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$58E14070-9E54-42BB-977C-00816FF61635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"786dbdc21c4ce4f1a2c00f1425f99efe0df79d07","datavalue":{"value":{"entity-type":"item","numeric-id":1894709,"id":"Q1894709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$BE62F6D2-35C1-486A-A01F-8EBB18BE3DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0670e8e22b9586945d2ea64cf1c9460849077d28","datavalue":{"value":{"entity-type":"item","numeric-id":2986892,"id":"Q2986892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$0D16BE2E-1D14-4188-9660-06FAEA218A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e96f7da718629afc44b34380a8ade0151b9225","datavalue":{"value":{"entity-type":"item","numeric-id":1944916,"id":"Q1944916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2334869$27AF896C-1B61-40FB-B1A3-5B4A14872755","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8bb163101834c0e2527835208f36aa4e829cc3e3","datavalue":{"value":"10.4007/ANNALS.2019.190.3.6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2334869$335C39FC-3B0F-4B47-8561-9CB3EE23A303","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c5741d0112fd38eb948857280b98e15f4ab8a93","datavalue":{"value":{"entity-type":"item","numeric-id":5123060,"id":"Q5123060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7543486ef97da9ff4c39efa2d8df12925992e5cb","datavalue":{"value":{"amount":"+0.867879331111908","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":"Q2334869$BA5B0385-15A7-4CA3-A2FF-7434A191FBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be4bdcfa3a42c9d3493a69fd769ced27c3a151ad","datavalue":{"value":{"entity-type":"item","numeric-id":1194759,"id":"Q1194759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a333ccb0d6c1520e79c9728ec35ead1d50c8a9c9","datavalue":{"value":{"amount":"+0.8646141886711121","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":"Q2334869$BC09C1CD-D2BC-4808-8262-C0FC6C62C318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aef6ec5d0bc71af07940cebb05674319d3af0a5","datavalue":{"value":{"entity-type":"item","numeric-id":2098195,"id":"Q2098195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f343b18cd8de026f0c3c03f4ea1a309d1db2ae9","datavalue":{"value":{"amount":"+0.8611614108085632","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":"Q2334869$E8E823B3-0A4C-480B-A197-47305670E077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e791433cbaa933ae9a24e65d49fec69c59845b31","datavalue":{"value":{"entity-type":"item","numeric-id":4636652,"id":"Q4636652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31b7322d1d5fcbf6a0ec1e8cc49fbdb53d8c4184","datavalue":{"value":{"amount":"+0.8601738214492798","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":"Q2334869$A3C6A3FB-B5CC-4D83-8312-8BDB8DD35CB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"272919a17bcc3df79c51b948da1a557caaba0f5e","datavalue":{"value":{"entity-type":"item","numeric-id":4598175,"id":"Q4598175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"392d0ea48705a499ac9260fdef5c6abffec81919","datavalue":{"value":{"amount":"+0.8332349061965942","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":"Q2334869$EB36DD34-9EFD-4990-806E-F154A588E827","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2334869","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2334869"}}}}}