<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
	"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
	<title>Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs | Beck | The Electronic Journal of Combinatorics</title>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<meta name="description" content="Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs" />
			<meta name="keywords" content="Golomb ruler; Sidon set; combinatorial reciprocity theorem; lattice point; inside-out polytope; Ehrhart quasipolynomial; mixed graph; proper coloring; acyclic orientation" />
	
	<link rel="icon" href="../../../../../public/journals/1/journalFavicon_en_US.ico" />
	<link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />

	<meta name="DC.Contributor.Sponsor" xml:lang="en" content=""/>
	<meta name="DC.Creator.PersonalName" content="Matthias Beck"/>
	<meta name="DC.Creator.PersonalName" content="Tristram Bogart"/>
	<meta name="DC.Creator.PersonalName" content="Tu Pham"/>
	<meta name="DC.Date.created" scheme="ISO8601" content="2012-10-04"/>
	<meta name="DC.Date.dateSubmitted" scheme="ISO8601" content="2012-09-24"/>
	<meta name="DC.Date.issued" scheme="ISO8601" content="2012-07-12"/>
	<meta name="DC.Date.modified" scheme="ISO8601" content="2012-10-04"/>
	<meta name="DC.Description" xml:lang="en" content=" 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\{ {\bf x} \in {\bf Z}^{m+1} : \, 0 = x_0 &amp;lt; x_1 &amp;lt; \dots &amp;lt; 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 ${\bf 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 ${\bf 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&#039;s reciprocity theorem for chromatic polynomials. Thus in the second part of the paper we develop an analogue of Stanley&#039;s theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations. "/>
	<meta name="DC.Format" scheme="IMT" content="application/pdf"/>		
	<meta name="DC.Identifier" content="v19i3p42"/>
	<meta name="DC.Identifier.pageNumber" content="P42"/>
		<meta name="DC.Identifier.URI" content="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p42"/>
	<meta name="DC.Language" scheme="ISO639-1" content=""/>
	<meta name="DC.Rights" content=" The copyright of published papers remains with the authors.  We only require your agreement that we publish it, as described in the following publication release agreement:    This is an agreement between the Electronic Journal of Combinatorics (the &quot;Journal&quot;), and the copyright owner (the &quot;Owner&quot;)     of a work (the &quot;Work&quot;) to be published in the Journal.  The Owner warrants that s/he has the full power and authority     to enter into this Agreement and to grant the rights granted in this     Agreement.   The Owner hereby grants to the Journal a worldwide, irrevocable,     royalty free license to publish or distribute the Work, to enter into            arrangements with others to publish or distribute the Work, and to     archive the Work.   The Owner agrees that further publication of the Work,     with the same or substantially the same content as appears in the     Journal, will include an acknowledgement of prior publication     in the Journal.  "/>
	<meta name="DC.Source" content="The Electronic Journal of Combinatorics"/>
	<meta name="DC.Source.ISSN" content="1077-8926"/>
	<meta name="DC.Source.Issue" content="3"/>
	<meta name="DC.Source.URI" content="http://www.combinatorics.org/ojs/index.php/eljc"/>
	<meta name="DC.Source.Volume" content="19"/>
						<meta name="DC.Subject" xml:lang="en" content="Golomb ruler"/>
								<meta name="DC.Subject" xml:lang="en" content="Sidon set"/>
								<meta name="DC.Subject" xml:lang="en" content="combinatorial reciprocity theorem"/>
								<meta name="DC.Subject" xml:lang="en" content="lattice point"/>
								<meta name="DC.Subject" xml:lang="en" content="inside-out polytope"/>
								<meta name="DC.Subject" xml:lang="en" content="Ehrhart quasipolynomial"/>
								<meta name="DC.Subject" xml:lang="en" content="mixed graph"/>
								<meta name="DC.Subject" xml:lang="en" content="proper coloring"/>
								<meta name="DC.Subject" xml:lang="en" content="acyclic orientation"/>
				<meta name="DC.Title" content="Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs"/>
		<meta name="DC.Type" content="Text.Serial.Journal"/>
	<meta name="DC.Type.articleType" content="Papers"/>	
		<meta name="gs_meta_revision" content="1.1" />
	<meta name="citation_journal_title" content="The Electronic Journal of Combinatorics"/>
	<meta name="citation_issn" content="1077-8926"/>
	<meta name="citation_authors" content="Beck, Matthias; Bogart, Tristram; Pham, Tu"/>
	<meta name="citation_title" content="Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs"/>

	<meta name="citation_date" content="04/10/2012"/>

	<meta name="citation_volume" content="19"/>
	<meta name="citation_issue" content="3"/>
	<meta name="citation_firstpage" content="P42"/>
		<meta name="citation_abstract_html_url" content="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p42"/>
						<meta name="citation_keywords" xml:lang="en" content="Golomb ruler"/>
								<meta name="citation_keywords" xml:lang="en" content="Sidon set"/>
								<meta name="citation_keywords" xml:lang="en" content="combinatorial reciprocity theorem"/>
								<meta name="citation_keywords" xml:lang="en" content="lattice point"/>
								<meta name="citation_keywords" xml:lang="en" content="inside-out polytope"/>
								<meta name="citation_keywords" xml:lang="en" content="Ehrhart quasipolynomial"/>
								<meta name="citation_keywords" xml:lang="en" content="mixed graph"/>
								<meta name="citation_keywords" xml:lang="en" content="proper coloring"/>
								<meta name="citation_keywords" xml:lang="en" content="acyclic orientation"/>
				<meta name="citation_pdf_url" content="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p42/pdf"/>
	

	<link rel="stylesheet" href="../../../../../lib/pkp/styles/pkp.css" type="text/css" />
	<link rel="stylesheet" href="../../../../../lib/pkp/styles/common.css" type="text/css" />
	<link rel="stylesheet" href="../../../../../styles/common.css" type="text/css" />
	<link rel="stylesheet" href="../../../../../styles/articleView.css" type="text/css" />
			<link rel="stylesheet" href="../../../../../lib/pkp/styles/rtEmbedded.css" type="text/css" />
	
	
	
	<link rel="stylesheet" href="../../../../../styles/sidebar.css" type="text/css" />		<link rel="stylesheet" href="../../../../../styles/rightSidebar.css" type="text/css" />	
			<link rel="stylesheet" href="../../../../../public/journals/1/journalStyleSheet.css" type="text/css" />
	
	<!-- Base Jquery -->
	<script type="text/javascript" src="http://www.google.com/jsapi"></script>
	<script type="text/javascript">
		// Provide a local fallback if the CDN cannot be reached
		if (typeof google == 'undefined') {
			document.write(unescape("%3Cscript src='http://www.combinatorics.org/ojs/lib/pkp/js/lib/jquery/jquery.min.js' type='text/javascript'%3E%3C/script%3E"));
			document.write(unescape("%3Cscript src='http://www.combinatorics.org/ojs/lib/pkp/js/lib/jquery/plugins/jqueryUi.min.js' type='text/javascript'%3E%3C/script%3E"));
		} else {
			google.load("jquery", "1.4.2");
			google.load("jqueryui", "1.8.1");
		}
	
</script>
	
	<script type="text/javascript" src="../../../../../lib/pkp/js/jquery.cookie.js"></script>
	<script type="text/javascript" src="../../../../../lib/pkp/js/fontController.js" ></script>
	<script type="text/javascript">
		$(function(){
			fontSize("#sizer", "body", 9, 16, 32, "/ojs"); // Initialize the font sizer
		});
	
</script>


	<script type="text/javascript" src="../../../../../lib/pkp/js/general.js"></script>
	
	<!-- MathJax plugin -->
		<script type="text/javascript"
			src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
                    MathJax.Hub.Config({
                       tex2jax: {
                        inlineMath: [ ["$","$"], ["\\(","\\)"] ],
                        displayMath: [ ["$$","$$"], ["\\[","\\]"] ],
                        processEscapes: true,
                        processEnvironments: true }
                       });
		</script>
	<!-- / MathJax plugin -->
	<script language="javascript" type="text/javascript" src="../../../../../js/articleView.js"></script>
	<script language="javascript" type="text/javascript" src="../../../../../js/pdfobject.js"></script>

</head>
<body>

<div id="container">
<div id="fade" class="black_overlay"></div>
<div id="header">
<div id="headerTitle">
<h1>
	<img src="../../../../../public/journals/1/pageHeaderTitleImage_en_US.png" width="744" height="137" alt="The Electronic Journal of Combinatorics" />
</h1>
</div>
</div>

<div id="body">

	<div id="sidebar">
							<div id="rightSidebar">
				<div class="block" id="sidebarHelp">
	<a class="blockTitle" href="javascript:openHelp('http://www.combinatorics.org/ojs/index.php/eljc/help')">Journal Help</a>
</div><div class="block" id="sidebarUser">
			<span class="blockTitle">User</span>
		
						<form method="post" action="http://www.combinatorics.org/ojs/index.php/eljc/login/signIn">
				<table>
					<tr>
						<td><label for="sidebar-username">Username</label></td>
						<td><input type="text" id="sidebar-username" name="username" value="" size="12" maxlength="32" class="textField" /></td>
					</tr>
					<tr>
						<td><label for="sidebar-password">Password</label></td>
						<td><input type="password" id="sidebar-password" name="password" value="" size="12" maxlength="32" class="textField" /></td>
					</tr>
					<tr>
						<td colspan="2"><input type="checkbox" id="remember" name="remember" value="1" /> <label for="remember">Remember me</label></td>
					</tr>
					<tr>
						<td colspan="2"><input type="submit" value="Log In" class="button" /></td>
					</tr>
				</table>
			</form>
			</div><div class="block" id="sidebarInformation">
	<span class="blockTitle">Information</span>
	<ul>
		<li><a href="../../../information/readers">For Readers</a></li>		<li><a href="../../../information/authors">For Authors</a></li>		<li><a href="../../../information/librarians">For Librarians</a></li>	</ul>
</div>


<div class="block" id="sidebarRTArticleTools">

	<span class="blockTitle">Article Tools</span>
			<div class="articleToolItem">
			<img src="../../../../../plugins/blocks/readingTools/icons/abstract.png" class="articleToolIcon" /> <a href="index.html" target="_parent">Abstract</a><br />
		</div>
							<div class="articleToolItem">
		<img src="../../../../../plugins/blocks/readingTools/icons/editorialPolicies.png" class="articleToolIcon" /> <a href="http://www.combinatorics.org/ojs/index.php/eljc/about/editorialPolicies#peerReviewProcess" target="_parent">Review policy</a>
	</div>
			<div class="articleToolItem">
			<img src="../../../../../plugins/blocks/readingTools/icons/emailArticle.png" class="articleToolIcon" />
			Email this article <span style="font-size: 0.8em">(Login required)</span>		</div>
				<div class="articleToolItem">
			<img src="../../../../../plugins/blocks/readingTools/icons/emailArticle.png" class="articleToolIcon" />
			Email the author <span style="font-size: 0.8em">(Login required)</span>		</div>
		</div>
 <div class="block" id="notification">
	<span class="blockTitle">Notifications</span>
	<ul>
					<li><a href="../../../notification">View</a></li>
			<li><a href="http://www.combinatorics.org/ojs/index.php/eljc/notification/subscribeMailList">Subscribe</a> / <a href="http://www.combinatorics.org/ojs/index.php/eljc/notification/unsubscribeMailList">Unsubscribe</a></li>	
			</ul>
</div>
<div class="block" id="sidebarNavigation">
	<span class="blockTitle">Journal Content</span>
	
	<span class="blockSubtitle">Search</span>
	<form method="post" action="http://www.combinatorics.org/ojs/index.php/eljc/search/results">
	<table>
	<tr>
		<td><input type="text" id="query" name="query" size="15" maxlength="255" value="" class="textField" /></td>
	</tr>
	<tr>
		<td><select name="searchField" size="1" class="selectMenu">
			<option label="All" value="">All</option>
<option label="Authors" value="1">Authors</option>
<option label="Title" value="2">Title</option>
<option label="Abstract" value="4">Abstract</option>
<option label="Index terms" value="120">Index terms</option>
<option label="Full Text" value="128">Full Text</option>

		</select></td>
	</tr>
	<tr>
		<td><input type="submit" value="Search" class="button" /></td>
	</tr>
	</table>
	</form>
	
	<br />
	
		<span class="blockSubtitle">Browse</span>
	<ul>
		<li><a href="../../../issue/archive">By Issue</a></li>
		<li><a href="../../../search/authors">By Author</a></li>
		<li><a href="../../../search/titles">By Title</a></li>
				<li><a href="../../../../index">Other Journals</a></li>
			</ul>
	</div>
<div class="block" id="sidebarFontSize" style="margin-bottom: 4px;">
	<span class="blockTitle">Font Size</span>
	<div id="sizer"></div>
</div>
<br />
			</div>
			</div>

<div id="main">

<div id="navbar">
	<ul class="menu">
		<li id="home"><a href="../../../index">Home</a></li>
		<li id="about"><a href="../../../about">About</a></li>

					<li id="login"><a href="../../../login">Log In</a></li>
							<li id="register"><a href="../../../user/register">Register</a></li>
										<li id="search"><a href="../../../search/index.html">Search</a></li>
		
					<li id="current"><a href="../../../issue/current">Current</a></li>
			<li id="archives"><a href="../../../issue/archive">Archives</a></li>
		
				

									<li id="navItem"><a href="../../../../../../issue/view/Surveys">SURVEYS</a></li>
											</ul>
</div>

<div id="breadcrumb">
	<a href="../../../index" target="_parent">Home</a> &gt;
	<a href="../../../issue/view/Volume19-3" target="_parent">Volume 19, Issue 3 (2012)</a> &gt;	<a href="pdf" class="current" target="_parent">P42</a>
</div>

<div id="content">

			
		
		<script type="text/javascript"><!--
			$(document).ready(function(){
				if ($.browser.webkit) { // PDFObject does not correctly work with safari's built-in PDF viewer
					var embedCode = "<object id='pdfObject' type='application/pdf' data='http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/v19i3p42/pdf' width='99%' height='99%'><div id='pluginMissing'><p>The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of <a href=\"http://www.adobe.com/products/acrobat/readstep2.html\">Adobe Acrobat Reader<\/a>).<\/p> <p>Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.<\/p> <p>If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful <a href=\"http://highwire.stanford.edu/help/pdf-faq.dtl\">Frequently Asked Questions about PDFs<\/a>.<\/p></div></object>";
					$("#articlePdf").html(embedCode);
					if($("#pluginMissing").is(":hidden")) {
						$('#fullscreenShow').show();
						$("#articlePdf").resizable({ containment: 'parent', handles: 'se' });
					} else { // Chrome Mac hides the embed object, obscuring the text.  Reinsert.
						$("#articlePdf").html('<p>The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of <a href=\"http://www.adobe.com/products/acrobat/readstep2.html\">Adobe Acrobat Reader<\/a>).<\/p> <p>Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.<\/p> <p>If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful <a href=\"http://highwire.stanford.edu/help/pdf-faq.dtl\">Frequently Asked Questions about PDFs<\/a>.<\/p>');
					}
				} else {
					var success = new PDFObject({ url: "http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/v19i3p42/pdf" }).embed("articlePdf");
					if (success) {
						// PDF was embedded; enbale fullscreen mode and the resizable widget
						$('#fullscreenShow').show();
						$("#articlePdfResizer").resizable({ containment: 'parent', handles: 'se' });
					}
				}
			});
		
		// -->
		
</script>
		<div id="articlePdfResizer">
			<div id="articlePdf" class="ui-widget-content">
				<p>The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of <a href="http://www.adobe.com/products/acrobat/readstep2.html">Adobe Acrobat Reader</a>).</p> <p>Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.</p> <p>If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful <a href="http://highwire.stanford.edu/help/pdf-faq.dtl">Frequently Asked Questions about PDFs</a>.</p>
			</div>
		</div>
		<p>
						<a class="action" target="_parent" href="../../download/v19i3p42/pdf">Download this PDF file</a>
			<a class="action" href="#" id="fullscreenShow">Fullscreen</a>
			<a class="action" href="#" id="fullscreenHide">Fullscreen Off</a>
		</p>
	





</div><!-- content -->
</div><!-- main -->
</div><!-- body -->



</div> <!-- container -->
</body>
</html>
