{"entities":{"Q6121105":{"pageid":13255412,"ns":120,"title":"Item:Q6121105","lastrevid":102472049,"modified":"2026-06-06T04:32:36Z","type":"item","id":"Q6121105","labels":{"en":{"language":"en","value":"Two proofs of Bondy's theorem on induced subsets and two related questions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7809277"}},"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":"Q6121105$8B720418-BE8B-4055-A6F6-D9FAE87EC2BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57c4fd9cda669c9e8b5016462adafb6735f28674","datavalue":{"value":{"text":"Two proofs of Bondy's theorem on induced subsets and two related questions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6121105$16E4488E-3CCE-4EDA-94BE-8E1FF747BA9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd73e7c3093d46115da4ca277fa231acec3332cb","datavalue":{"value":{"entity-type":"item","numeric-id":2410137,"id":"Q2410137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$E46C388B-D3F4-4D9E-AD83-5D65F971CB9A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"255223deab9a614645300983eff9e9b445f432d0","datavalue":{"value":{"entity-type":"item","numeric-id":207920,"id":"Q207920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$528E5079-83F8-47E7-B214-96F56AAEC18F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f159de156c29b3b40d3f017379c75305e2772f01","datavalue":{"value":{"time":"+2024-02-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6121105$BFF071D4-4531-4FB3-A015-99FB6C962A2E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e237d0b2ed792bc321302a46123abb800c08696c","datavalue":{"value":"In this short note, the author gives two short proofs of the following theorem by Bondy:  If \\(F=\\{A_1, A_2, \\ldots, A_n\\} \\subseteq \\mathcal{P}(A)\\) is a family of \\(n\\) distinct subsets of an \\(n\\)-set \\(A\\), then there is an \\(\\alpha \\in A\\) such that the sets \\(A_i \\setminus \\alpha\\), where \\(1 \\leq i \\leq n\\), are all distinct.  The first proof uses the contrapositive: If \\(F=\\{A_1, A_2, \\ldots, A_n\\} \\subseteq \\mathcal{P}(A)\\) is a family of \\(n\\) subsets of an \\(n\\)-set \\(A\\), such that for every \\(\\alpha \\in A\\) the sets \\(A_i \\setminus \\alpha\\), where \\(1 \\leq i \\leq n\\), are not all distinct, then not all the sets in \\(F\\) are distinct.  For this, construct a graph on \\([n]\\) and for every \\(\\alpha\\), add an edge \\((i,j)\\) for a pair for which \\(A_i \\setminus \\alpha= A_j \\setminus \\alpha.\\) Then this graph has a cycle (possible a digon), implying that the sets corresponding to the vertices of the cycle are all equal.  The second proof uses linear algebra to prove the theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121105$788CC9B6-6F4B-4D78-B1E5-62605EDB8DBE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9ea4d24f04e3dffb4771216003ffd35c847cbe39","datavalue":{"value":{"entity-type":"item","numeric-id":820841,"id":"Q820841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$87B176AF-CABE-4FCB-BEB3-923E80E13219","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9bd9af688c0b97c53a0660570659cd00420d9c9b","datavalue":{"value":"05D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$3A86406D-E03F-444A-97C1-7F98291B9BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$61935AC0-BAF4-4CB7-8840-ABC61B83B17E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$0720F512-6B00-4E14-838A-D4312EF2FEA5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a25c48e12ee7cd97f9b95edcfff61bb5f3dc03ee","datavalue":{"value":"7809277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$8D8F69AA-D933-429A-BC6D-88B04AE112B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57edc9dc97568085b95ef12ac8f2ada17c7077bf","datavalue":{"value":"distinct subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q6121105$D9CC364B-7F60-4270-9992-EF86C3F96152","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":"Q6121105$9339CA75-F5CB-4458-BB7B-2292F0C64C2B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1fc9003af20a270de3bc385cec73598228507a7b","datavalue":{"value":"Q113692019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$8B055E5A-3BAB-4DE6-B09D-A7BDCEFC98C0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dfd6145850d410071255220fb9022ba3d389f811","datavalue":{"value":"https://doi.org/10.4171/em/486","type":"string"},"datatype":"url"},"type":"statement","id":"Q6121105$6E298E6C-3825-4113-851D-0B3904BFF2EE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"84bd75eda453b0c4aaf0e1af38eb23f89bbc5d23","datavalue":{"value":"W4294091438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$1100093D-F11A-4061-96CF-B7490020260E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5250e02486a79ebd69be420413de5224ca74ad21","datavalue":{"value":{"entity-type":"item","numeric-id":3741626,"id":"Q3741626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$5D688E31-C988-42BB-BA3B-F352FCF38951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c67cd1fc5f79128afc0722554e08faf0c36cc03","datavalue":{"value":{"entity-type":"item","numeric-id":3726125,"id":"Q3726125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$E74CABF5-3480-4E52-9922-50D233AA664E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"643d954aab38b2b70adf9f785895084f4c0093bc","datavalue":{"value":{"entity-type":"item","numeric-id":2544367,"id":"Q2544367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$D381365F-A59F-418D-BBB8-BFBA3188E989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"338a4be1049d4ae99518addf5c42f6d1f049f468","datavalue":{"value":{"entity-type":"item","numeric-id":1971019,"id":"Q1971019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6121105$A7B9B331-F548-4331-BEB8-F0C6E721AC82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8210b708a5b0e6a323d1a79f93b49e1b8dbe2186","datavalue":{"value":"10.4171/EM/486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6121105$332A76FE-DDAF-4420-A6D3-E48BD44F2DD0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efeff9a38e51f03e86650e5a4fd9bc7546e4a3ed","datavalue":{"value":{"entity-type":"item","numeric-id":1971019,"id":"Q1971019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7df67f56fcd68bb5b60ae5d6f87dbee1870844f0","datavalue":{"value":{"amount":"+0.9011486768722534","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":"Q6121105$761A05A0-1A1A-4456-AA76-50E15C55C7F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0502cc75e52a1438b28012010a53beaa6a0f8b3e","datavalue":{"value":{"entity-type":"item","numeric-id":4201564,"id":"Q4201564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b75b4dc766787437aa61979f79bd6ad3b6bf218a","datavalue":{"value":{"amount":"+0.7585090398788452","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":"Q6121105$6405D59F-C35D-4D81-A148-0204B6DA0405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdf0e642d954cfb06de830fca044bc9dc7e9b19a","datavalue":{"value":{"entity-type":"item","numeric-id":5937251,"id":"Q5937251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ac089e36d703fc2792e1b050290cd9e085cbee9","datavalue":{"value":{"amount":"+0.703591525554657","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":"Q6121105$7623D53D-85CC-4B14-820F-070A0BF4897A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7854345b02cd11337ee29026cbfdc0730efdeab2","datavalue":{"value":{"entity-type":"item","numeric-id":5599180,"id":"Q5599180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fbf946ba4326acf2ee656477da4049cb584f085","datavalue":{"value":{"amount":"+0.6989301443099976","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":"Q6121105$CCB85A23-5177-4DFD-83D1-9E55689656A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f156dc565213d61496f963f83794614f4efcce01","datavalue":{"value":{"entity-type":"item","numeric-id":809102,"id":"Q809102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c29eac37599aa3df69b3fb98a0406daee933ab5e","datavalue":{"value":{"amount":"+0.6928326487541199","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":"Q6121105$51E6D29A-D17A-4EA8-B09D-5BC458931B97","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two proofs of Bondy's theorem on induced subsets and two related questions","badges":[]}}}}}