{"entities":{"Q668015":{"pageid":669864,"ns":120,"title":"Item:Q668015","lastrevid":63519552,"modified":"2026-04-11T13:43:12Z","type":"item","id":"Q668015","labels":{"en":{"language":"en","value":"Independent sets in the union of two Hamiltonian cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7032054"}},"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":"Q668015$C907F18F-0C4B-4ACB-8424-792B94F6636E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9101ecbf97f9cd709205262f6f3495240b460efb","datavalue":{"value":{"text":"Independent sets in the union of two Hamiltonian cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q668015$6C217580-B37D-4D2C-821F-2E116AE62700","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d084c7dc12ae059d12dba9aeefd3c4345d935441","datavalue":{"value":"1409.05111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$D3DF826C-2E95-4047-B3AC-4B93310AE923","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f050d7429f1445acd3d9c3e3fe97add9db84e6f4","datavalue":{"value":{"entity-type":"item","numeric-id":186189,"id":"Q186189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$A2EF3044-65BE-4365-89D8-62DE315FEE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6967e9e4538b05f5f7236f5a9185c533d27fc6c","datavalue":{"value":{"entity-type":"item","numeric-id":526275,"id":"Q526275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$F98B31C7-6FDB-4A28-BC30-3E1767BECF37","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$BBA7DF6E-8BD7-4ED6-A95C-08326714C9A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c236a5296bce37f0e3594963375752714d7f6e86","datavalue":{"value":{"time":"+2019-03-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q668015$27FA299D-9818-4F42-AE64-D92E67AF2DB1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6bfbf3ed637245a670a27c0f5557639ae43f72c5","datavalue":{"value":"https://arxiv.org/abs/1609.09746","type":"string"},"datatype":"url"},"type":"statement","id":"Q668015$8C1CA850-9C1C-453F-8700-627720EAC784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"511c6082c26ed896c9f02226c045b973807a5f4f","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p48","type":"string"},"datatype":"url"},"type":"statement","id":"Q668015$59B33505-6C93-431F-AEF7-FF137ABE6A2F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7877c32aad84a1b405dc23d5e184577e7993b4f4","datavalue":{"value":"Summary: Motivated by a question on the maximal number of vertex disjoint Schrijver graphs in the Kneser graph, we investigate the following function, denoted by \\(f(n,k)\\): the maximal number of Hamiltonian cycles on an \\(n\\) element set, such that no two cycles share a common independent set of size more than \\(k\\). We shall mainly be interested in the behavior of \\(f(n,k)\\) when \\(k\\) is a linear function of \\(n\\), namely \\(k=cn\\). We show a threshold phenomenon: there exists a constant \\(c_t\\) such that for \\(c<c_t\\), \\(f(n,cn)\\) is bounded by a constant depending only on \\(c\\) and not on \\(n\\), and for \\(c_t <c\\), \\(f(n,cn)\\) is exponentially large in \\(n (n \\rightarrow \\infty)\\). We prove that \\(0.26 < c_t < 0.36\\), but the exact value of \\(c_t\\) is not determined. For the lower bound we prove a technical lemma, which for graphs that are the union of two Hamiltonian cycles establishes a relation between the independence number and the number of \\(K_4\\) subgraphs. A corollary of this lemma is that if a graph \\(G\\) on \\(n>12\\) vertices is the union of two Hamiltonian cycles and \\(\\alpha(G)=n/4\\), then \\(V(G)\\) can be covered by vertex-disjoint \\(K_4\\) subgraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q668015$4848AB40-5AB4-4AB2-9C66-D8523C6F6A82","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$CF968589-003A-490C-9778-143295A58C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$3D02EDC2-1A09-47BF-853D-95ACBA7D17A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$D4A07355-7211-4765-95B6-CFF9C17525AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$F6CBC17C-C59A-4605-BE4A-A509F8CC1F14","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dfd659af60e0a5f000254b2fc3ed2594b103a43a","datavalue":{"value":"7032054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$01DFA5B9-4FB0-4F17-8C0F-84B74EF6E3AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q668015$369A456B-DD08-4D7B-8860-DFE4C9772213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q668015$A6D160C1-8F86-4773-AEF8-CA2E779122E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa43ca26aebd8ae0638b42530721325719fa4e11","datavalue":{"value":"union","type":"string"},"datatype":"string"},"type":"statement","id":"Q668015$FE5CC1C8-EB4B-4485-810C-74DD9D16A1E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1e9df5f6f5000b0a9065b89a898b5d7f1ccfbfe","datavalue":{"value":"threshold","type":"string"},"datatype":"string"},"type":"statement","id":"Q668015$DE2B55FE-62C6-47EC-A299-C143DC597753","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":"Q668015$12E9576C-C5A7-4420-856A-3F14EA74F60D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b41da683081378fbdb7a6cde8e39f82c87277d9a","datavalue":{"value":{"entity-type":"item","numeric-id":4111622,"id":"Q4111622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$3FAAA985-4BE6-49E9-BB39-8F09CC08B5F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$9330B127-F44E-4029-800A-56BD0D04545C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52c7540760fe9ef3923a27be3c87c2aba62dfedc","datavalue":{"value":{"entity-type":"item","numeric-id":1149967,"id":"Q1149967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$287D2C3F-BCD9-4373-9D3B-078F542B1B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$4CE66866-24CE-4422-B441-417EF8ECF296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff83d10746962b696cefc78ae39ea40c1e5727ea","datavalue":{"value":{"entity-type":"item","numeric-id":1386480,"id":"Q1386480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$040D9633-05C4-4F47-8BF5-045346544185","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":"Q668015$75263197-224E-4057-8F80-1ED9CBCC28E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d531e6338d21d1d0d4fd03e1bab6896c8316fa9b","datavalue":{"value":{"entity-type":"item","numeric-id":3869375,"id":"Q3869375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668015$FA54C464-6866-4BF9-B43F-FA6ABADF5CE1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"38801b2c97813e334de12502147330cb8c03bfe0","datavalue":{"value":"bafkreig45uzljiybffle6it5jje37uhrijummimczekpduhklpqxfacmiu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668015$C9CB350F-40D7-4909-ACC4-FB462FBF3BF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"573876b1b7dda12b0d5ac0704d0ece50e21b4b15","datavalue":{"value":{"entity-type":"item","numeric-id":4683325,"id":"Q4683325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d2af5ced60df41537738a6c6846df4f7be1a28e","datavalue":{"value":{"amount":"+0.7865012884140015","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":"Q668015$B1D8F9C0-920D-46A3-8C11-3E3B602DA637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb0e73f0046dd88a4faee20b544e8959c0b75115","datavalue":{"value":{"entity-type":"item","numeric-id":1910587,"id":"Q1910587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbecad9c1c49269357c793efdcf8c69b528a6dcb","datavalue":{"value":{"amount":"+0.7709118723869324","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":"Q668015$9FCD6149-31B2-49A6-80CF-41EEB543C757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b732fcfdf98d29c11dc77d0ee4b37fd07cac5b10","datavalue":{"value":{"entity-type":"item","numeric-id":2846630,"id":"Q2846630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbecad9c1c49269357c793efdcf8c69b528a6dcb","datavalue":{"value":{"amount":"+0.7709118723869324","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":"Q668015$FE7D956C-47A4-486F-967E-1408ED74DD03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04841948fb0c4e4680c3701b8dd37023b5caec48","datavalue":{"value":{"entity-type":"item","numeric-id":3469119,"id":"Q3469119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a1d2dc652715f1d6f07ea25a5eb46898a4caf78","datavalue":{"value":{"amount":"+0.7632049918174744","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":"Q668015$338F6946-DBCD-49B7-97A9-561FA185B9AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eeed3e7e8c32f18a54e2f327fe1228accb4aba0","datavalue":{"value":{"entity-type":"item","numeric-id":5492569,"id":"Q5492569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27220691e068654f378ce2c71b33932e7866306a","datavalue":{"value":{"amount":"+0.7609238624572754","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":"Q668015$E76F9F2A-C353-4F63-8728-7329623272C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independent sets in the union of two Hamiltonian cycles","badges":[]}}}}}