{"entities":{"Q456386":{"pageid":458153,"ns":120,"title":"Item:Q456386","lastrevid":62093637,"modified":"2026-04-11T03:43:19Z","type":"item","id":"Q456386","labels":{"en":{"language":"en","value":"Enumeration of Golomb rulers and acyclic orientations of mixed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6098384"}},"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":"Q456386$BC78B278-2D66-4FFC-A965-2FF6F239014F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fd6d18938d28abd40496d518592dbb361819ea46","datavalue":{"value":{"text":"Enumeration of Golomb rulers and acyclic orientations of mixed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q456386$9E869803-4822-4F4F-ABEE-C2E360DF1711","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"107fef6ddcb34ad9ee6f25e217dc7cef28b183d6","datavalue":{"value":"1253.05014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$42196600-AF85-4465-9239-4E354EA2CC75","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"107f30e329cd74707502050fc61d35d6b810cba6","datavalue":{"value":{"entity-type":"item","numeric-id":372825,"id":"Q372825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456386$DAE4A096-E8C3-45CD-BE9F-5194173118F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"306bde872240114061360abe5f498cac402d1d07","datavalue":{"value":{"entity-type":"item","numeric-id":1747994,"id":"Q1747994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456386$AB2A38C1-D1EB-4961-859D-9B7A526C5460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da47379d55df6e2071c568b7d9dd6923d2565dbb","datavalue":{"value":{"entity-type":"item","numeric-id":6085583,"id":"Q6085583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456386$BDCA3E0B-D762-42DB-A938-1F7A50E54E0C","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":"Q456386$BE8D98A9-1F65-433A-A5AA-232D0F95497A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ee92d50481ed05c06549abf63f6ece88b90dd74","datavalue":{"value":{"time":"+2012-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q456386$61078611-92D7-4CCF-B54C-1A7F5C0321EB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1be8aafce884894991ace0072dca9794446616f7","datavalue":{"value":"https://arxiv.org/abs/1110.6154","type":"string"},"datatype":"url"},"type":"statement","id":"Q456386$11C5EBEF-C276-4983-AE21-54E2BF2ED410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"db76475afda36841475d9c926b031fad0fcaee31","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p42","type":"string"},"datatype":"url"},"type":"statement","id":"Q456386$3A8FE4DB-69C7-41A9-B46E-9D0B34D5AC54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f9a8f86b74f39bf2376c2805a9009f3a6b284a5","datavalue":{"value":"Summary: A Golomb ruler is a sequence of distinct integers (the markings of the ruler) whose pairwise differences are distinct. Golomb rulers, also known as Sidon sets and \\(B_2\\) sets, can be traced back to additive number theory in the 1930s and have attracted recent research activities on existence problems, such as the search for optimal Golomb rulers (those of minimal length given a fixed number of markings). Our goal is to enumerate Golomb rulers in a systematic way: we study  \\[ g_m(t) := \\# \\left\\{ {\\mathbf x} \\in {\\mathbb Z}^{m+1} : \\, 0 = x_0 < x_1 < \\dots < x_m = t , \\text{ all } x_j - x_k \\text{ distinct} \\right\\}, \\]  the number of Golomb rulers with \\(m+1\\) markings and length \\(t\\).Our main result is that \\(g_m(t)\\) is a quasipolynomial in \\(t\\) which satisfies a combinatorial reciprocity theorem: \\((-1)^{m-1} g_m(-t)\\) equals the number of rulers \\({\\mathbf x}\\) of length \\(t\\) with \\(m+1\\) markings, each counted with its Golomb multiplicity, which measures how many combinatorially different Golomb rulers are in a small neighborhood of \\({\\mathbf x}\\). Our reciprocity theorem can be interpreted in terms of certain mixed graphs associated to Golomb rulers; in this language, it is reminiscent of Stanley's reciprocity theorem for chromatic polynomials. Thus in the second part of the paper we develop an analogue of Stanley's theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$94BD318C-9B86-4F97-B44F-079139687AA5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$C4CBC5F8-1DEF-4434-AC90-A0F5F2C6B46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$FE09B384-392B-4352-93F0-B92EC8584261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a9a3cc9d8dbe21daf76270a263ac1d6ebdfc38d1","datavalue":{"value":"11P21","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$6334D4D1-204C-47EE-B848-4C30414B76BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7501cba48320d715aa2f92c8f7803347a8901b66","datavalue":{"value":"52C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$353DA265-82AB-4106-ACDF-4D0B45265DE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d96fa7659ae2782267cb50bec552daa04fceae7","datavalue":{"value":"6098384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$8F44AD26-6327-48C8-A514-D8F79F06A21F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd5989c470cca8dbc561b036092891f925704a84","datavalue":{"value":"Golomb ruler","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$7C7CE121-B1C6-428D-AF3F-C769826FE17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea812fabae60f79755fee25626776dff83ead5ea","datavalue":{"value":"Sidon set","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$D39D46BE-CEFC-4C72-AD4E-43BA5B06D68E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5275a850902527556c90a9a8c8d705f1b361e52c","datavalue":{"value":"combinatorial reciprocity theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$BCF6B4E6-E48E-4D99-8C64-9EFBF1E1160B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03cbaa017e8fda7584fb448e003ecb149201d2d4","datavalue":{"value":"lattice point","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$44025BDC-468F-4F7F-8701-2B9172F3DDB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1473f9696a5b97beda865c079db6422c280d005c","datavalue":{"value":"inside-out polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$BC20AF14-2C07-4423-B48C-3D4DEB93B304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b6ae559fafdc66c20c736cfdfad6bc1c5ee09c7","datavalue":{"value":"Ehrhart quasipolynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$1C1D6808-4381-4AAD-89EB-288E00CD573F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"015ebba32123e37a03edcacb6fbc442a513b22c4","datavalue":{"value":"mixed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$ED328201-B297-4E5A-A5A4-C6847E786F94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a59ba2750774c4fe5438f914dd85e56cf4c0b57","datavalue":{"value":"proper coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$31D690DF-D0EE-4074-AB14-62E6C2B97EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd08082ecfb3b93b17c9a46ab514e0f78e6b2bec","datavalue":{"value":"acyclic orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q456386$F06E7EAE-3FA8-48CF-803C-DF265F86870B","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":"Q456386$0F932583-329B-48F3-AAFD-17B38407A597","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"04308f8aec2ef74180f3a5d1becb3667f40bcc5c","datavalue":{"value":"bafkreihl6quujgkvnvt4b5xajrfc4ympgigys2mx3mwyl672s2ltdfxthe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456386$480C9A44-4A31-40AD-9C4D-B0E35AC50BBE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b94d3aa57ebf8d72938a68b8a10d3a5ee736d679","datavalue":{"value":{"entity-type":"item","numeric-id":3129826,"id":"Q3129826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90430206f7e2714c920164c21a62991d18dd173d","datavalue":{"value":{"amount":"+0.8864114","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":"Q456386$787BADD6-F586-41AC-92F7-FE92C8ACF800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0756d6a9e0c24f43be24f6766d29b9c70b152c8","datavalue":{"value":{"entity-type":"item","numeric-id":5264718,"id":"Q5264718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f700c98db09b5badf21ff9244c30a973906e014","datavalue":{"value":{"amount":"+0.87842214","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":"Q456386$206C849F-8B57-4177-AC12-9228004356D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9bf74b874488874b5a1bbcd93cc1f35d87b4150","datavalue":{"value":{"entity-type":"item","numeric-id":5937454,"id":"Q5937454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4563160cf6c578ccd8848d4e19a7d209b30d6d17","datavalue":{"value":{"amount":"+0.87777036","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":"Q456386$881D2466-9AE2-4CCC-9636-EA24BD553FD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ddfc978250f15b527df58c4e17f7d0247b10cd0","datavalue":{"value":{"entity-type":"item","numeric-id":5952156,"id":"Q5952156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd2c163c9b1c7b225d19b39ed1c7127428cf300b","datavalue":{"value":{"amount":"+0.87345034","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":"Q456386$111F5728-5A32-42D3-B4E1-E6B2F46D18DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"015924aa166e9d7e91622ebd496312f6d0a73591","datavalue":{"value":{"entity-type":"item","numeric-id":5957358,"id":"Q5957358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bed428a43a5f2ba58a480b90bd09456ec5962906","datavalue":{"value":{"amount":"+0.8708328","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":"Q456386$9BF10F2B-38C2-4EDD-83E8-F73733C82656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e29ff8512c883cebeea4000afd4194d41b14208","datavalue":{"value":{"entity-type":"item","numeric-id":3328565,"id":"Q3328565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"397a8d8fb46f553d43a68a7a6ee23dc49c285a41","datavalue":{"value":{"amount":"+0.87068164","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":"Q456386$0D92AF11-A720-4FB8-8773-2D7C2D6E67F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6162a1cb3b1e1fd48d4f9431e6f2154be91793a3","datavalue":{"value":{"entity-type":"item","numeric-id":2563513,"id":"Q2563513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbc066e3760a688987f5b7d0c13857d5a63c3b99","datavalue":{"value":{"amount":"+0.8695508","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":"Q456386$F953B68E-977A-4C81-9B97-E83F62956FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fd764f2370864a9ba25da738759271ee49687e7","datavalue":{"value":{"entity-type":"item","numeric-id":3537203,"id":"Q3537203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39af3072521501007ee39073ba19837d9173338b","datavalue":{"value":{"amount":"+0.86531687","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":"Q456386$59C551E9-F28D-4F6A-990E-08297BAF325D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78807a8001a167e6343c109fa689045493f55d87","datavalue":{"value":{"entity-type":"item","numeric-id":2798221,"id":"Q2798221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b1c0d6731ccd0dcbd772808300f2e47bf07690c","datavalue":{"value":{"amount":"+0.86342615","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":"Q456386$F192422A-8F64-44AE-8616-85E86653B29F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6da47fd9182a12be3466e71ccccfd0b99312f4de","datavalue":{"value":{"entity-type":"item","numeric-id":3768909,"id":"Q3768909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d63e1088fa783c8b1735bf2db5151d079204064","datavalue":{"value":{"amount":"+0.8630183","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":"Q456386$4B325F1A-A4C3-406F-926D-22557FB78CE7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Enumeration of Golomb rulers and acyclic orientations of mixed graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Enumeration_of_Golomb_rulers_and_acyclic_orientations_of_mixed_graphs"}}}}}