{"entities":{"Q1641004":{"pageid":1651745,"ns":120,"title":"Item:Q1641004","lastrevid":71629386,"modified":"2026-04-13T23:30:40Z","type":"item","id":"Q1641004","labels":{"en":{"language":"en","value":"Short proofs of the Kneser-Lov\u00e1sz coloring principle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6889859"}},"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":"Q1641004$7226DBF3-BFB6-4B7E-8AC7-BCC744CFC712","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4bb4fdc7dd7be2a42fdf2967efbef127ba3733e0","datavalue":{"value":{"text":"Short proofs of the Kneser-Lov\u00e1sz coloring principle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1641004$9B78808D-9A0D-46BF-8DB9-571E825F1F91","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5de5ef6c92dac837b951b8279e925956ab5c35b4","datavalue":{"value":"1443.03040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$0A8BCC3C-4D8C-4CD2-A4E7-E9EF628AEF37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37ff12306afde6b4869bcc5cf6c739b73ca0cc28","datavalue":{"value":{"entity-type":"item","numeric-id":1641002,"id":"Q1641002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$C57E7C6A-8720-4A9D-BA99-23B8F5A412BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e092db0e8dd3eb069452d08315b921747f610dc1","datavalue":{"value":{"entity-type":"item","numeric-id":360041,"id":"Q360041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$FC00CCE2-4F9B-48A4-8524-8EE786193407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"556b5f897f5d545f04c26b56d4624f5cc4b2661a","datavalue":{"value":{"entity-type":"item","numeric-id":195654,"id":"Q195654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$9BA00CC9-AEA4-427A-81A5-3818E0D1AC6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1003c4f09725aecca735f79d55fdefb06ed2cd61","datavalue":{"value":{"entity-type":"item","numeric-id":865640,"id":"Q865640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$EBB16416-1376-42DD-B80D-6604CF5C2960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b88ab3fb71a4aafb294f7c8f5ef994c2050fce86","datavalue":{"value":{"entity-type":"item","numeric-id":1194654,"id":"Q1194654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$50CE7437-51AB-430B-9CF8-2680BACE1ED4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$2B0254E8-A080-498A-9F9B-CD88349AEA7C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b559bb800700d5ba2a45f57085de6ba33131f78","datavalue":{"value":{"time":"+2018-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1641004$E0CC3CEC-F4C5-48CC-8241-9B2953BFB07B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2898982bc683a85185b022adf3de77d6c716c731","datavalue":{"value":"http://hdl.handle.net/2117/124274","type":"string"},"datatype":"url"},"type":"statement","id":"Q1641004$6EF3D03C-15A8-437F-B066-5289FFA95379","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"364b58a386b330cb93612e18a9f6cd0353627209","datavalue":{"value":"One of the long-standing open problems in proof complexity is to separate the \\textit{Frege} and \\textit{extended Frege} (EF) proof systems; even though it is commonly believed that extended Frege should have exponential speed-up over Frege, not even a superlinear separation has been proved. A part of the problem is that we do not even know of good \\textit{candidates} for tautologies that have polynomial-size EF proofs, but plausibly require exponential-size Frege proofs. (Here, we are looking for simple combinatorial tautologies rather than reflection principles and the like, as it is assumed that the latter are unlikely to be amenable to direct lower bound techniques.) While various examples have been proposed, virtually all of them turned out to have polynomial or quasipolynomial Frege proofs.  \\textit{G. Istrate} and \\textit{A. Cr\u00e3ciun} [Lect. Notes Comput. Sci. 8561, 138--153 (2014; Zbl 1423.03243)] proposed tautologies expressing the \\textit{Kneser-Lov\u00e1sz theorem}, which gives a tight lower bound on the chromatic number of the Kneser graphs \\(K(n,k)\\) (whose vertices are \\(k\\)-element subsets of \\([n]\\), and edges connect disjoint sets). For fixed \\(k\\), this can be expressed by propositional formulas (DNF) of size polynomial in \\(n\\). Common proofs of the Kneser--Lov\u00e1sz theorem employ topological or other high-level methods, which are not readily formalizable in weak proof systems.  The main result of the present paper is that for any constant \\(k\\), the Kneser-Lov\u00e1sz tautologies have polynomial EF proofs, and quasipolynomial Frege proofs (hence they cannot yield a more than quasipolynomial separation between Frege and EF). This is shown by an infinite descent argument using elementary counting, which gradually reduces the general case to the base case of constant-size \\(n\\) (roughly \\(n\\le k^4\\)); the latter has a constant-size brute-force Frege proof just because the Kneser-Lov\u00e1sz theorem is true in the real world.  While this is not indicated in the paper, the argument shows that for constant \\(k\\), the Kneser-Lov\u00e1sz theorem is provable in the bounded arithmetical theory \\(S^1_2\\) (by the EF argument), and even in \\(R^1_2\\) (by the Frege argument).  Since the non-uniformity of the proof of the base case is unsatisfactory, the authors explore other approaches that might lead to better proofs. They introduce \\textit{truncated Tucker lemma} tautologies, and show that the Kneser-Lov\u00e1sz tautologies have poly-size constant-depth Frege derivations from the truncated Tucker lemma. However, the proof complexity of the truncated Tucker lemma tautologies themselves remains largely unknown: the authors only show that they have poly-size EF proofs in the simplest \\(k=1\\) case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1641004$1A1CA38D-BD40-4572-96BB-B31C51E8D68B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf05c748b19f894b0cb445a65a1da1ca24dbc809","datavalue":{"value":{"entity-type":"item","numeric-id":331053,"id":"Q331053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$2EC1B105-1278-40A2-B781-46CFF6E9AA3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$48D476C5-52F0-4067-9637-A1BD499650E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$9C5AF63D-9D2E-48E2-A9EE-59D5EE2381EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45e8b1b68cdab56303c5f2d3f306729c169772a3","datavalue":{"value":"6889859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$EC6EB28D-D213-45A9-9A45-9294C651DBA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"986e975208b070c5142b42b7967bb38dc4fad0f4","datavalue":{"value":"proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1641004$F97DB79C-B796-49DF-A264-5149EDA50657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38f64e3457e4e7acae043ba514e80ec3e98a76bc","datavalue":{"value":"extended Frege","type":"string"},"datatype":"string"},"type":"statement","id":"Q1641004$DA325820-C1DE-40DB-9FFB-6297C36A4377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de2523347144db8f827bb70bce45694d1b91f0ec","datavalue":{"value":"Kneser-Lov\u00e1sz theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1641004$0011988D-DE32-46B0-8ACB-F827F25AE7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1641004$CB70BF9F-FD23-4B14-A0CE-7F40AB0CEA52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"508d1c26f278bbbd1edeb423462633d8dae7552d","datavalue":{"value":"Tucker lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1641004$B067EA49-900C-4AD1-A209-A3859993F528","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":"Q1641004$3269F775-8F59-4D08-9A93-48C7DCA2C897","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ad53c2e6117a7e9b4d9603653e7480d0f708de3f","datavalue":{"value":"W2790199059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$8C05DCF3-47F9-404A-A1B8-C21354FE46AB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"80662bf7f4e1e750ba6ea06b0d426a5c1e5f5373","datavalue":{"value":"Q113872845","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$72E8CE07-3099-42B3-BDF9-A5E201CC3052","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8114c211fca5bae4eaebfd4e040f702bba8b2dce","datavalue":{"value":{"entity-type":"item","numeric-id":3449464,"id":"Q3449464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$8446387E-CAF5-400B-9666-6D0C530B3040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e5d95d4a1f501517f04217bc5b6894d0b0c5d5f","datavalue":{"value":{"entity-type":"item","numeric-id":4375783,"id":"Q4375783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$582DA460-C54C-4494-A4BC-577C11A4F405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeebd466643aa876c1932f0bfc7bb13b63abb5a2","datavalue":{"value":{"entity-type":"item","numeric-id":5410329,"id":"Q5410329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$C33CE4A8-3BB4-46F1-90C8-1B235114D34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cb5c2591c3b4779c32d742e1061633a99acbed","datavalue":{"value":{"entity-type":"item","numeric-id":4850545,"id":"Q4850545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$F75CA476-A8B8-4D98-9973-C319AF068ACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4efc758b393bfca7e5de457ca3a2ef28a58c2b55","datavalue":{"value":{"entity-type":"item","numeric-id":2344736,"id":"Q2344736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$A8763F4F-FE44-4B42-AFF9-01A0EA069BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"035feb3d68e7fcb8cc1f5afc2267fb8cc293e0bf","datavalue":{"value":{"entity-type":"item","numeric-id":3794177,"id":"Q3794177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$90C23393-6008-4235-83C6-D55C18C1DCAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f31cbeafb74eb2331031a6d2305fa02411af3e7","datavalue":{"value":{"entity-type":"item","numeric-id":3775553,"id":"Q3775553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$00137D56-917D-4CDD-ADB1-7ACC2358638C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"268508f11a93ad9daf989654e9defbf367898cdf","datavalue":{"value":{"entity-type":"item","numeric-id":1177033,"id":"Q1177033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$BD9F0F8B-E0C4-45FA-BB8B-AF6D93080A78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"822e3104d6a40cfdd4c15d4f4c0a6e67edb1c659","datavalue":{"value":{"entity-type":"item","numeric-id":4263835,"id":"Q4263835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$ADCCABA3-13A7-44C7-8A82-19F61B037B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aa0d6b54f6be3a440a4bb5a78e5668dceeb60c0","datavalue":{"value":{"entity-type":"item","numeric-id":435190,"id":"Q435190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$6ACF0CA2-BB3E-41DE-965E-D5C76BAC7AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a549ed1d776396be3e4308655e166de224ba89","datavalue":{"value":{"entity-type":"item","numeric-id":4133141,"id":"Q4133141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$4CD33C55-2494-4DAD-9BA1-FEE3EF0C3FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81494301ed40478ad47563138f01784b63003971","datavalue":{"value":{"entity-type":"item","numeric-id":4152212,"id":"Q4152212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$D112876A-F8F4-41A7-9D77-CB26C504ED38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$09EDF9F2-A5A9-47FE-8F2C-260094257802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"519c04edb24aef1ce88b720e46082a964b292326","datavalue":{"value":{"entity-type":"item","numeric-id":3281090,"id":"Q3281090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$B58D4B2D-892D-480A-A446-EFBAF49445FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a90104c97733fb25f66ac0187735bd78d4eb845","datavalue":{"value":{"entity-type":"item","numeric-id":1069937,"id":"Q1069937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$19DE4E56-B2D6-4816-A6A1-8C0B14843A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56482c6dd29359d39b50f1d0751fcaf2df2ea9e","datavalue":{"value":{"entity-type":"item","numeric-id":1153158,"id":"Q1153158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$B5D4C426-CBDE-4299-981E-818AABDC3736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4db718337c47f930eac480f7f0beee5c7871d7","datavalue":{"value":{"entity-type":"item","numeric-id":5554997,"id":"Q5554997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$31356F8F-BB32-4F09-9FB9-8732ACFEECB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a94b866c4904c0fee0380e2ce17f042631fee90","datavalue":{"value":{"entity-type":"item","numeric-id":5252690,"id":"Q5252690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$4ECD60BF-A9E6-4318-80E8-030011FFA4CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b59b02c873aea56e9b357d14638711873259a51","datavalue":{"value":{"entity-type":"item","numeric-id":3192060,"id":"Q3192060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$DB14270A-66E5-4B83-A3AE-4353FC8D57A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ccdc2885bcd85970cf2540be17a7b4af1868eaa","datavalue":{"value":{"entity-type":"item","numeric-id":1887654,"id":"Q1887654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$C15AADDF-699C-4F83-B31D-072AC6E141BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05d95378a8c31d7715b88a9854f2b8f7d5953534","datavalue":{"value":{"entity-type":"item","numeric-id":639650,"id":"Q639650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$F8EC3B4E-1BB4-47E3-95A3-46E337F264FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fa34ae3e34f6a863a9f8db67c2bfb8bb6401943","datavalue":{"value":{"entity-type":"item","numeric-id":4856172,"id":"Q4856172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$BCEF8EC2-4EE4-4C38-BE4D-D1498BEF7421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c428f1852e95384416608cd782a84ad75e86d42b","datavalue":{"value":{"entity-type":"item","numeric-id":755592,"id":"Q755592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$7EFBF78C-4347-4452-BFE6-734454BFA4CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c697ac96dcb6d8ce9d9417ec4d5d18c7e16de713","datavalue":{"value":{"entity-type":"item","numeric-id":1882147,"id":"Q1882147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$9D775ABC-A703-47C8-899F-512D7F5ACFA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a35ee073efb257c2ff6944a7cc91fcd0fe8bb82","datavalue":{"value":{"entity-type":"item","numeric-id":1329155,"id":"Q1329155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$44857CD5-6247-4A31-88EA-E7AA57AD3709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16379452a4949bf4e97a3cd79c6104d4a7ee9465","datavalue":{"value":{"entity-type":"item","numeric-id":3755452,"id":"Q3755452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$3B67C08B-7F11-4465-A700-E712B13ECE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11c8e8c45bd30e4d2779b4e28bf2c174478c03fb","datavalue":{"value":{"entity-type":"item","numeric-id":3773878,"id":"Q3773878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$3D875BC5-E9AC-4895-A3E7-076541694838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd902b6160e42565c7d2c676094d64283d352a8","datavalue":{"value":{"entity-type":"item","numeric-id":5444711,"id":"Q5444711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$094CC7EE-19A5-4895-B342-92ABADEC8878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86d053b9add83a4b6a0158d11a7705ba5eb1ce5f","datavalue":{"value":{"entity-type":"item","numeric-id":3882451,"id":"Q3882451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$E3EAE6C8-EC6C-4973-B5A8-F9C3B84B7629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e05b0528b2c08afdc6214ddb7fca5da686e0954e","datavalue":{"value":{"entity-type":"item","numeric-id":1608563,"id":"Q1608563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1641004$82A87001-CC37-4382-8909-D348D046EBFF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cd420a0e6154cd6b146fea7246d3220dc92bf9b8","datavalue":{"value":"10.1016/J.IC.2018.02.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1641004$49765DED-227A-496A-B291-8BA52CD49C53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07e262e6c8a90326aab9a6e0db87e79f4096b202","datavalue":{"value":{"entity-type":"item","numeric-id":3449464,"id":"Q3449464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","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":"Q1641004$3AA5A762-3486-4DBA-9E41-D76E6562B2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fc836205db1a4af178a07522ef07f2d43ea88e0","datavalue":{"value":{"entity-type":"item","numeric-id":2441638,"id":"Q2441638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"401fddcd2653fc1377cc2fc3289b18c647507df4","datavalue":{"value":{"amount":"+0.90923923","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":"Q1641004$794C3ADE-8545-4EDC-8A23-45686F7F4EE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff2b01e25ddc59e6b21e8d6504798dd2838faea1","datavalue":{"value":{"entity-type":"item","numeric-id":1758510,"id":"Q1758510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f34a0b2848c5e6118e540c7d2cf867a5ff6ac2cb","datavalue":{"value":{"amount":"+0.90645987","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":"Q1641004$D0A52E17-7573-4843-85E3-C2DF25C45E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"383b8c93a22a39a4fb1b2238f734141d1e60e440","datavalue":{"value":{"entity-type":"item","numeric-id":1608563,"id":"Q1608563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49a7f2dceae583e8bd1a7d43ef8fbb3f56fa2442","datavalue":{"value":{"amount":"+0.90206105","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":"Q1641004$F8FDFBEE-1A50-4373-A00D-B1C35CCDEC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e4c65a5388d85634311c70c24f0d94d07ecac45","datavalue":{"value":{"entity-type":"item","numeric-id":1405112,"id":"Q1405112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d18dabd4202b94de46db6d4c8bdfd8c1928506a","datavalue":{"value":{"amount":"+0.8834938","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":"Q1641004$09FD01BC-88EB-4E19-AA16-EBAE8AFE29F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93d3a3846f5072c97a0b5ebf05fe7ff9aec22800","datavalue":{"value":{"entity-type":"item","numeric-id":3737489,"id":"Q3737489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae4e0341af7f47b5e51a559f02ce0d3cad3b8347","datavalue":{"value":{"amount":"+0.88167596","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":"Q1641004$32AD5EFD-8EEA-4622-9120-BF8A78200946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5de2eaedc45d466a6f2818edb8837f89838eb85a","datavalue":{"value":{"entity-type":"item","numeric-id":1807552,"id":"Q1807552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2523263421f436cead253f630ebec7df8c8bff5","datavalue":{"value":{"amount":"+0.8781767","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":"Q1641004$E1F480FB-C853-44E4-8494-52492AF1FD93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aee8dee38cfa45429a806d833304a209b162732","datavalue":{"value":{"entity-type":"item","numeric-id":3484859,"id":"Q3484859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90bfe0f1548e7c41da456fb49aa1946bec3bf8e0","datavalue":{"value":{"amount":"+0.8776859","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":"Q1641004$ED31C0CD-9A98-4C2C-8A49-87D6B293E250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d18d20e3756ed4a14b12241ee0a1f164228e2ca8","datavalue":{"value":{"entity-type":"item","numeric-id":3015575,"id":"Q3015575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a527491e626b98dde87d64ce66c295e1044c6e3","datavalue":{"value":{"amount":"+0.87720585","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":"Q1641004$A68180ED-277E-4911-8873-D1F3AAD42E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c888289bd4ed5d6332d3121dd257cd427ee39728","datavalue":{"value":{"entity-type":"item","numeric-id":1318810,"id":"Q1318810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e919a429b2010bcc6d276504bc3a22506fbc8257","datavalue":{"value":{"amount":"+0.875345","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":"Q1641004$E223A773-1955-4FDE-A21F-1C095F5D8686","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Short proofs of the Kneser-Lov\u00e1sz coloring principle","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Short_proofs_of_the_Kneser-Lov%C3%A1sz_coloring_principle"}}}}}