An upper bound on the number of high-dimensional permutations

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an n×n×...×n=[n] ^d+1 array of zeros and ones in which every line contains a unique 1 entry. A line here is a set of entries of the form {(x ₁,...,x _i?1,y,x _i+1,...,x _d+1)|n≥y≥1} for some index d+1≥i≥1 and some choice of x _j ∈ [n] for all j ≠ i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number $$\left( {(1 + o(1))\frac{n} {{e^d }}} \right)^{n^d } .$$ We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Brégman’s [1] proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Schrijver’s [11] and Radhakrishnan’s [10] proofs of Brégman’s theorem.     

Inversion polynomials for 321-avoiding permutations

We prove a generalization of a conjecture of Dokos, Dwyer, Johnson, Sagan, and Selsor giving a recursion for the inversion polynomial of 321-avoiding permutations. We also answer a question they posed about finding a recursive formula for the major index polynomial of 321-avoiding permutations. Other properties of these polynomials are investigated as well. Our tools include Dyck and 2-Motzkin paths, polyominoes, and continued fractions.     

A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c. Let Δ^* be the maximum face degree of a graph. There exist plane graphs with χ^c = ?3/2 Δ^*?. Ore and Plummer [ 5 ] proved that χ^c ≤ 2, Δ^*, which bound was improved to ?9/5, Δ^*? by Borodin, Sanders, and Zhao [ 1 ], and to ?5/3,Δ^*? by Sanders and Zhao [ 7 ]. We introduce a new parameter k^*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c ≤ max {Δ^* + 3,k^* + 2, Δ^* + 14, 3, k^* + 6, 18}, and if Δ^* ≥ 4 and k^* ≥ 4, then χ^c ≤ Δ^* + 3,k^* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

An upper bound on the number of planarK-sets

Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane that separatesX fromS–X. We prove thatO(nk/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.The research of J. Pach was supported in part by NSF Grant CCR-8901484 and by Grant OTKA-1418 from the Hungarian Foundation for Scientific Research. The research of W. Steiger and E. Szemerédi was supported in part by NSF Grant CCR-8902522. All authors express gratitude to the NSF DIMACS Center at Rutgers.     

An upper bound on the number of frequency hypercubes

A frequency n-cube $F^n(q;l_0,...,l_{m-1})$ is an n-dimensional q-by-...-by-q array, where $q=l_0+...+l_{m-1}$, filled by numbers $0,...,m-1$ with the property that each line contains exactly $l_i$ cells with symbol i, $i=0,...,m-1$ (a line consists of q cells of the array differing in one coordinate). The trivial upper bound on the number of frequency n-cubes is $m^{{(q-1)}^n}$. We improve that lower bound for $n>2$, replacing $q-1$ by a smaller value s, by constructing a testing set of size $s^n$ for frequency n-cubes (a testing set is a collection of cells of an array the values in which uniquely determine the array with given parameters). We also construct new testing sets for generalized frequency n-cubes, which are essentially correlation-immune functions in n q-valued arguments; the cardinalities of new testing sets are smaller than for testing sets known before.     

An upper bound for the number of matroids

An upper bound for the number of matroids is obtained. This upper bound complements the lower bound obtained by Piff and Welsh in [1].     

An upper bound on the number of Steiner triple systems

Richard Wilson conjectured in 1974 the following asymptotic formula for the number of n ‐vertex Steiner triple systems: \begin{align*} STS(n) = \left( (1+o(1))\frac{n}{e^2} \right)^{\frac{n^2}{6}}\end{align*}. Our main result is that The proof is based on the entropy method. As a prelude to this proof we consider the number F(n) of 1 ‐factorizations of the complete graph on n vertices. Using the Kahn‐Lovász theorem it can be shown that We show how to derive this bound using the entropy method. Both bounds are conjectured to be sharp. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 399–406, 2013     

An upper bound on the independence number of benzenoid systems

Recently, the graph theoretic independence number has been linked to fullerene stability [S. Fajtlowicz, C. Larson, Graph-theoretic independence as a predictor of fullerene stability, Chem. Phys. Lett. 377 (2003) 485-490; S. Fajtlowicz, Fullerene Expanders, A list of Conjectures of Minuteman, Available from S. Fajtlowicz: math0@bayou.uh.edu]. In particular, stable fullerenes seem to minimize their independence numbers. A large piece of evidence for this hypothesis comes from the fact that stable benzenoids—close relatives of fullerenes—do minimize their independence numbers [S. Fajtlowicz, “Pony Express”—Graffiti's conjectures about carcinogenic and stable benzenoids, 〈http://www.math.uh.edu/∼siemion/pony.html〉]. In this paper, an upper bound on the independence number of benzenoids is introduced and proven—giving a limit on how large the independence ratio for benzenoids can be. In conclusion, this bound on independence is correlated to an upper bound on the number of unpaired sites a benzenoid system has with respect to a maximum matching, which is precisely the number of zero eigenvalues in the spectrum of the adjacency matrix (due to a conjecture of Graffiti and its proof by Sachs [S. Fajtlowicz, “Pony Express”—Graffiti's conjectures about carcinogenic and stable benzenoids, 〈http://www.math.uh.edu/∼siemion/pony.html〉; H. Sachs, P. John, S. Fajtlowicz, On Maximum Matchings and Eigenvalues of Benzenoid Graphs, preprint—MATCH]). Thus, since zero eigenvalues and unpaired sites are indicative of instability (reactivity), we get a simple but intuitive bound on how reactive a benzenoid molecule can be.     

An upper bound for the total chromatic number

The total chromatic number,(G), of a graphG, is defined to be the minimum number of colours needed to colour the vertices and edges of a graph in such a way that no adjacent vertices, no adjacent edges and no incident vertex and edge are given the same colour. This paper shows that , where(G) is the vertex chromatic number and(G) is the edge chromatic number of the graph.Partially supported by ORS grant ORS/84120     

An upper bound on the path number of a digraph

A proof is presented of the conjecture of Alspach and Pullman that for any digraph G on n ≥ 4 vertices, the path number of G is at most [$\text{n}{}^2\text{4}$].     

An upper bound for the restricted online Ramsey number

The restricted $(m,n;N)$-online Ramsey game is a game played between two players, Builder and Painter. The game starts with $N$ isolated vertices. Each turn Builder picks an edge to build and Painter chooses whether that edge is red or blue, and Builder aims to create a red $K_m$ or blue $K_n$ in as few turns as possible. The restricted online Ramsey number $\stackrel{?}{r}(m,n;N)$ is the minimum number of turns that Builder needs to guarantee her win in the restricted $(m,n;N)$-online Ramsey game. We show that if $N=r(n,n)$, $\stackrel{?}{r}(n,n;N)\le \left(\genfrac{}{}{0ex}{}{N}{2}\right)?\Omega (NlogN),$motivated by a question posed by Conlon, Fox, Grinshpun and He. The equivalent game played on infinitely many vertices is called the online Ramsey game. As almost all known Builder strategies in the online Ramsey game end up reducing to the restricted setting, we expect further progress on the restricted online Ramsey game to have applications in the general case.     

An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.     

Pattern-restricted permutations composed of 3-cycles

In this paper, we characterize and enumerate pattern-avoiding permutations composed of only 3-cycles. In particular, we answer the question for the six patterns of length 3. We find that the number of permutations composed of n 3-cycles that avoid the pattern 231 (equivalently 312) is given by $3^{n?1}$, while the generating function for the number of those that avoid the pattern 132 (equivalently 213) is given by a formula involving the generating functions for the well-known Motzkin numbers and Catalan numbers. The number of permutations composed of n 3-cycles that avoid the pattern 321 is characterized by a weighted sum involving statistics on Dyck paths of semilength n.     

An upper bound for the k-domination number of a graph

The k-domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).     

An upper bound for the chromatic number of line graphs

It was conjectured by Reed [B. Reed, ω,α, and χ, Journal of Graph Theory 27 (1998) 177–212] that for any graph G, the graph’s chromatic number χ(G) is bounded above by , where Δ(G) and ω(G) are the maximum degree and clique number of G, respectively. In this paper we prove that this bound holds if G is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph G and produces a colouring that achieves our bound.