{"entities":{"Q1197014":{"pageid":1207763,"ns":120,"title":"Item:Q1197014","lastrevid":47103547,"modified":"2025-12-31T16:42:26Z","type":"item","id":"Q1197014","labels":{"en":{"language":"en","value":"Indecomposable regular graphs and hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89890"}},"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":"Q1197014$0435B84F-ABCB-4D45-9BE8-1607B6D21F65","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e1d861e0354d51c70f7594104fa4b20a49620642","datavalue":{"value":{"text":"Indecomposable regular graphs and hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1197014$372C1467-8F0E-4232-BC01-E37878E9A87A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"818b01b0be32f18b49825f7dcb13b6506532ebf0","datavalue":{"value":"0755.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197014$016B1A2C-C20C-4143-AE2A-D90FBEAEF452","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b7d5cadc1a9b05d8da1dd1e4829b2d6b8eea331","datavalue":{"value":"10.1016/0012-365X(92)90590-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197014$3D45E337-7A47-4C59-BB7C-0755AADF258C","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":"Q1197014$B7FD150B-75E6-493C-A0F7-2338E7B21353","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1197014$716037B6-DE29-42BA-8078-4337A0F74ED6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f0975945c150c5ba25d5d0bb2c4137303720e7c6","datavalue":{"value":"A hypergraph \\(H\\) consists of a finite nonempty set \\(V(H)\\) called the vertex set and a collection \\(E(H)\\) (called the edge set of \\(H)\\) of subsets of the power set of \\(V(H)\\). Note \\(E(H)\\) may contain the same set more then once. The number of times an element \\(e\\) in \\(E(H)\\) appears in \\(E(H)\\) is called its multiplicity denoted by \\(m_ H(e)\\). If each edge of \\(H\\) appears exactly once in \\(E(H)\\), \\(H\\) is said to be a simple hypergraph. A hypergraph is a \\(k\\)-uniform hypergraph if each edge contains \\(k\\) elements. The 2-uniform hypergraphs are graphs. The degree of a vertex \\(v\\) in \\(H\\) is defined by \\(\\deg_ H(v)=\\Sigma(m_ H(e)\\mid v\\in e\\in E(H))\\). The hypergraph \\(H\\) is \\(d\\)-regular if \\(\\deg_ H(v)=d\\) for all \\(v\\in V(H)\\). A subhypergraph is a spanning subhypergraph if \\(\\cup E(F)=\\cup E(H)\\). The hypergraph \\(H\\) is indecomposable if it contains no proper non-empty regular spanning subhypergraph. It is shown that if \\(d>\\sqrt n-1\\) and if \\(G\\) is a simple \\(d\\)-regular graph on \\(n\\) vertices, then \\(G\\) contains a proper regular spanning subhypergraph; and if \\(G\\) is a \\(d\\)-regular multigraph with \\(n\\) vertices such that \\(d>(n-1)/3\\), then \\(G\\) contains a proper regular spanning subgraph. It is shown that these bounds are sharp for odd \\(d\\). For \\(n\\geq k\\geq 1\\), \\(D(n,k)\\) is the maximum possible \\(d\\) such that there exists a \\(d\\)-regular indecomposable \\(k\\)- uniform hypergrah on \\(n\\) vertices. Alon and Berman conjectured that \\(D(n,k)\\leq n^{c(k)}\\) where \\(c(k)\\) depends on \\(k\\) only. This conjecture is disproved in this paper by constructing examples that show that \\(D(n,3)\\geq 2^{(n-6)/2}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$D1A8DA04-4E1E-4288-9D6D-D2C9F035AE73","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197014$D22BA736-595E-4899-8A67-EC1815B3F271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197014$3489D971-13E1-4110-A771-0549FE00E87C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e297e5fee54765cfa4f4674d1f3530091d064caf","datavalue":{"value":"89890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197014$48A5403D-5DAB-4840-B86D-5D9F0D5B42E0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$72AB9DFF-379B-4411-8918-2BA9EB9614EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$18E7A5F8-DFC3-4F82-93BF-2011934F4DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$0C63EE2F-AAE3-49A9-A854-F1DADDF5E0DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8a0db09a63aeb1f72747bd60b79d4765e8a3932","datavalue":{"value":"multiplicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$0F2331B2-CF98-4123-9596-98E23B8530C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0f294a4316b947139f9345db579a1eb3ee7eab5","datavalue":{"value":"simple hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$B35AAE2D-5A10-4C67-8AE2-73A568533858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01b6ba51497b37286e1d2bbe9cd4b17058f32ecf","datavalue":{"value":"regular spanning subhypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197014$76CE732C-A0FB-4FA4-B1A4-EC72655834A7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"947071be942dac18e853a747b6abc41c36475503","datavalue":{"value":{"entity-type":"item","numeric-id":787137,"id":"Q787137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$47E453C1-7F61-4EAC-B73F-21B4982ACDC5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$9A12F5F7-8232-44EE-A76E-AC0D7550C131","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":"Q1197014$1C5EB02A-EE46-4511-9EC3-2352670D6423","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8924a2008248af40abd962604bbec5197fc18582","datavalue":{"value":{"entity-type":"item","numeric-id":1087559,"id":"Q1087559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$D9E902E0-528A-401F-81B2-4841BEAA8A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$2BEE72C1-0708-41C6-866F-373D4ECB7573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd77d1fbc3c3585d04500e3d9743b2f951baf630","datavalue":{"value":{"entity-type":"item","numeric-id":5202214,"id":"Q5202214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$0C73E2EB-F4D2-41BD-A8CD-8226FB020243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0a982efc813f01670ba472ad1a53be399b3fc72","datavalue":{"value":{"entity-type":"item","numeric-id":3346336,"id":"Q3346336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$3D21C6B1-9921-4203-A204-A817E2633C67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56103933925793a82a5672860532362beb2d750e","datavalue":{"value":{"entity-type":"item","numeric-id":4063467,"id":"Q4063467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$A40D6EE1-4F58-41AF-888E-ED4F3E8AF461","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"875f9d6c729c135c405d3c18f9dbb6389283e26b","datavalue":{"value":{"entity-type":"item","numeric-id":3710533,"id":"Q3710533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$7AA3EB90-BB15-4B2C-BB48-E4FA0CFB59B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$6410C576-07A3-4DCC-8DE3-C8998DE39EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8607df36f72dafcea2f3ab546bdb43c376a629a1","datavalue":{"value":{"entity-type":"item","numeric-id":1198642,"id":"Q1198642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$11357B0F-EB48-4312-AE86-7C78F9BF4F77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c80a69b6195da07678b4545abe9ce12891a5a11","datavalue":{"value":{"entity-type":"item","numeric-id":4750685,"id":"Q4750685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197014$5DA6A26C-5A2E-4EA5-B3C0-B461D6FD7BB9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c838ddf1ec544bc61ca4e7fc291706494273bd12","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)90590-c","type":"string"},"datatype":"url"},"type":"statement","id":"Q1197014$D72806AF-86A1-4578-879D-BCB967B2F5BF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"261b7079bea5ac7c2fb920134fb2e8068187ee4a","datavalue":{"value":"W2080495191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197014$71943469-E0F5-4D52-B56D-39214C95CEDF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4c59540bb2657255aaaaf2caf02432de96f7a39","datavalue":{"value":{"entity-type":"item","numeric-id":273181,"id":"Q273181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdc9c4afaacc8243d2879279d1e85d872ad46079","datavalue":{"value":{"amount":"+0.8162491917610168","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":"Q1197014$0A1D7B61-1054-4A58-916B-E19AF438CCA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8864c912cb41b1dfd3611b687a4572a819ad43b","datavalue":{"value":{"entity-type":"item","numeric-id":1026004,"id":"Q1026004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c025e3e8466afdd5337d48219029f43d7b334960","datavalue":{"value":{"amount":"+0.8131440281867981","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":"Q1197014$4F389CD6-A8D0-483E-8200-5D819B349F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05622b7dad1e85b80b39f62ab2451d0f890425b1","datavalue":{"value":{"entity-type":"item","numeric-id":1682214,"id":"Q1682214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baa9e6132f6219d01e585857fab290da36028d03","datavalue":{"value":{"amount":"+0.8032368421554565","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":"Q1197014$29FD8C8B-BF83-40DE-9EEA-425B20107C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1200d6ab8f23c74c95ab5b47274a8bdae8b7aa6d","datavalue":{"value":{"entity-type":"item","numeric-id":2442274,"id":"Q2442274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f51905f2ed8d330e91251494c4cae0697a432adc","datavalue":{"value":{"amount":"+0.8017065525054932","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":"Q1197014$1FF6EF28-AE97-4205-A119-E33D15DC83AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6670eeb974c0f586c221241a2823118de5055bb9","datavalue":{"value":{"entity-type":"item","numeric-id":3325764,"id":"Q3325764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b14f267be5b747a07c94107c2a9284a22b3835a","datavalue":{"value":{"amount":"+0.779081404209137","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":"Q1197014$CD3668ED-B82E-4D27-B22A-E2DA9BDFF9F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1197014","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1197014"}}}}}