The Electronic Journal of Combinatorics

The Lowest-Degree Polynomial with Nonnegative Coefficients Divisible by the $n$-th Cyclotomic Polynomial

John P. Steinberger — Thu, 18 Oct 2012 00:00:00 +1100

We pose the question of determining the lowest-degree polynomial with nonnegative coefficients divisible by the $n$-th cyclotomic polynomial $\Phi_n(x)$. We show this polynomial is $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$ where $p$ is the smallest prime dividing $n$ whenever $2/p > 1/q_1 + \cdots + 1/q_k$, where $q_1, \ldots, q_k$ are the other (distinct) primes besides $p$ dividing $n$. Determining the lowest-degree polynomial with nonnegative coefficients divisible by $\Phi_n(x)$ remains open in the general case, though we conjecture the existence of values of $n$ for which this degree is, in fact, less than $(p-1)n/p$.

Constructions of Bipartite and Bipartite-regular Hypermaps

Rui Duarte — Thu, 18 Oct 2012 00:00:00 +1100

A hypermap is bipartite if its set of flags can be divided into two parts A and B so that both A and B are the union of vertices, and consecutive vertices around an edge or a face are contained in alternate parts. A bipartite hypermap is bipartite-regular if its set of automorphisms is transitive on A and on B.

In this paper we see some properties of the constructions of bipartite hypermaps described algebraically by Breda and Duarte in 2007 which generalize the construction induced by the Walsh representation of hypermaps. As an application we show that all surfaces have bipartite-regular hypermaps.

Invariant Principal Order Ideals under Foata’s Transformation

Teresa X.S. Li, Melissa Y.F. Miao — Thu, 18 Oct 2012 00:00:00 +1100

Let $\Phi$ denote Foata's second fundamental transformation on permutations. For a permutation $\sigma$ in the symmetric group $S_n$, let $\widetilde{\Lambda}_{\sigma}=\{\pi\in S_n\colon\pi\leq_{w} \sigma\}$ be the principal order ideal generated by $\sigma$ in the weak order $\leq_{w}$. Björner and Wachs have shown that $\widetilde{\Lambda}_{\sigma}$ is invariant under $\Phi$ if and only if $\sigma$ is a 132-avoiding permutation. In this paper, we consider the invariance property of $\Phi$ on the principal order ideals ${\Lambda}_{\sigma}=\{\pi\in S_n\colon \pi\leq \sigma\}$ with respect to the Bruhat order $\leq$. We obtain a characterization of permutations $\sigma$ such that ${\Lambda}_{\sigma}$ are invariant under $\Phi$. We also consider the invariant principal order ideals with respect to the Bruhat order under Han's bijection $H$. We find that ${\Lambda}_{\sigma}$ is invariant under the bijection $H$ if and only if it is invariant under the transformation $\Phi$.

Some Constant Weight Codes from Primitive Permutation Groups

Derek H. Smith, Roberto Montemanni — Thu, 18 Oct 2012 00:00:00 +1100

In recent years the detailed study of the construction of constant weight codes has been extended from length at most 28 to lengths less than 64. Andries Brouwer maintains web pages with tables of the best known constant weight codes of these lengths. In many cases the codes have more codewords than the best code in the literature, and are not particularly easy to improve. Many of the codes are constructed using a specified permutation group as automorphism group. The groups used include cyclic, quasi-cyclic, affine general linear groups etc. sometimes with fixed points. The precise rationale for the choice of groups is not clear.

In this paper the choice of groups is made systematic by the use of the classification of primitive permutation groups. Together with several improved techniques for finding a maximum clique, this has led to the construction of 39 improved constant weight codes.

Rainbow Connection of Sparse Random Graphs

Alan Frieze, Charalampos E. Tsourakakis — Thu, 18 Oct 2012 00:00:00 +1100

An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected.

In this work we study the rainbow connectivity of binomial random graphs at the connectivity threshold $p=\frac{\log n+\omega}{n}$ where $\omega=\omega(n)\to\infty$ and ${\omega}=o(\log{n})$ and of random $r$-regular graphs where $r \geq 3$ is a fixed integer. Specifically, we prove that the rainbow connectivity $rc(G)$ of $G=G(n,p)$ satisfies $rc(G) \sim \max\{Z_1,\text{diam}(G)\}$ with high probability (whp). Here $Z_1$ is the number of vertices in $G$ whose degree equals 1 and the diameter of $G$ is asymptotically equal to $\frac{\log n}{\log\log n}$ whp. Finally, we prove that the rainbow connectivity $rc(G)$ of the random $r$-regular graph $G=G(n,r)$ whp satisfies $rc(G) =O(\log^{2\theta_r}{n})$ where $\theta_r=\frac{\log (r-1)}{\log (r-2)}$ when $r\geq 4$ and $rc(G) =O(\log^4n)$ whp when $r=3$.

Uniquely $K_r$-Saturated Graphs

Stephen G. Hartke, Derrick Stolee — Thu, 18 Oct 2012 00:00:00 +1100

A graph $G$ is uniquely $K_r$-saturated if it contains no clique with $r$ vertices and if for all edges $e$ in the complement, $G+e$ has a unique clique with $r$ vertices. Previously, few examples of uniquely $K_r$-saturated graphs were known, and little was known about their properties. We search for these graphs by adapting orbital branching, a technique originally developed for symmetric integer linear programs. We find several new uniquely $K_r$-saturated graphs with $4 \leq r \leq 7$, as well as two new infinite families based on Cayley graphs for $\mathbb{Z}_n$ with a small number of generators.

On Extensions of the Alon-Tarsi Latin Square Conjecture

Daniel Kotlar — Thu, 25 Oct 2012 09:43:18 +1100

Expressions involving the product of the permanent with the $(n-1)^{st}$ power of the determinant of a matrix of indeterminates, and of (0,1)-matrices, are shown to be related to an extension to odd dimensions of the Alon-Tarsi Latin Square Conjecture, first stated by Zappa. These yield an alternative proof of a theorem of Drisko, stating that the extended conjecture holds for Latin squares of odd prime order. An identity involving an alternating sum of permanents of (0,1)-matrices is obtained.

Orientations, Semiorders, Arrangements, and Parking Functions

Sam Hopkins, David Perkinson — Thu, 25 Oct 2012 00:00:00 +1100

It is known that the Pak-Stanley labeling of the Shi hyperplane arrangement provides a bijection between the regions of the arrangement and parking functions. For any graph $G$, we define the $G$-semiorder arrangement and show that the Pak-Stanley labeling of its regions produces all $G$-parking functions.

The Closed Knight Tour Problem in Higher Dimensions

Joshua Erde, Bruno Golénia, Sylvain Golénia — Thu, 25 Oct 2012 00:00:00 +1100

The problem of existence of closed knight tours for rectangular chessboards was solved by Schwenk in 1991. Last year, in 2011, DeMaio and Mathew provide an extension of this result for $3$-dimensional rectangular boards. In this article, we give the solution for $n$-dimensional rectangular boards, for $n\geq 4$.

Maximum Frustration in Bipartite Signed Graphs

Garry S Bowlin — Thu, 25 Oct 2012 00:00:00 +1100

A signed graph is a graph where each edge is labeled as either positive or negative. A circle is positive if the product of edge labels is positive. The frustration index is the least number of edges that need to be removed so that every remaining circle is positive. The maximum frustration of a graph is the maximum frustration index over all possible sign labellings. We prove two results about the maximum frustration of a complete bipartite graph $K_{l,r}$, with $l$ left vertices and $r$ right vertices. First, it is bounded above by\[ \frac{lr}{2}\left(1-\frac{1}{2^{l-1}}\binom{l-1}{\lfloor \frac{l-1}{2}\rfloor}\right).\] Second, there is a unique family of signed $K_{l,r}$ that reach this bound. Using this fact, exact formulas for the maximum frustration of $K_{l,r}$ are found for $l \leq 7$.

Repetition Threshold for Circular Words

Irina A. Gorbunova — Thu, 25 Oct 2012 00:00:00 +1100

We find the threshold between avoidable and unavoidable repetitions in circular words over $k$ letters for any $k\ge6$. Namely, we show that the number $CRT(k)=\frac{\left\lceil {k/2}\right\rceil{+}1}{\left\lceil {k/2}\right\rceil}$ satisfies the following properties. For any $n$ there exists a $k$-ary circular word of length $n$ containing no repetition of exponent greater than $CRT(k)$. On the other hand, $k$-ary circular words of some lengths must have a repetition of exponent at least $CRT(k)$.

Hypohamiltonian Graphs and their Crossing Number

Carol T. Zamfirescu — Thu, 25 Oct 2012 00:00:00 +1100

We prove that for every $k \ge 0$ there is an integer $n_0(k)$ such that, for every $n \ge n_0$, there exists a hypohamiltonian graph which has order $n$ and crossing number $k$.

Spectral Properties of Unitary Cayley Graphs of Finite Commutative Rings

Xiaogang Liu, Sanming Zhou — Thu, 25 Oct 2012 00:00:00 +1100

Let $R$ be a finite commutative ring. The unitary Cayley graph of $R$, denoted $G_R$, is the graph with vertex set $R$ and edge set $\left\{\{a,b\}:a,b\in R, a-b\in R^\times\right\}$, where $R^\times$ is the set of units of $R$. An $r$-regular graph is Ramanujan if the absolute value of every eigenvalue of it other than $\pm r$ is at most $2\sqrt{r-1}$. In this paper we give a necessary and sufficient condition for $G_R$ to be Ramanujan, and a necessary and sufficient condition for the complement of $G_R$ to be Ramanujan. We also determine the energy of the line graph of $G_R$, and compute the spectral moments of $G_R$ and its line graph.

Locally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness

Edward A. Bender, E. Rodney Canfield, Zhicheng Gao — Thu, 25 Oct 2012 00:00:00 +1100

We define the notion of asymptotically free for locally restricted compositions, which means roughly that large parts can often be replaced by any larger parts. Two well-known examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part, number of distinct parts and number of parts of multiplicity $k$, all accurate to $o(1)$.

New Proofs of Determinant Evaluations Related to Plane Partitions

Hjalmar Rosengren — Thu, 25 Oct 2012 00:00:00 +1100

We give a new proof of a determinant evaluation due to Andrews, which has been used to enumerate cyclically symmetric and descending plane partitions. We also prove some related results, including a $q$-analogue of Andrews's determinant.