Search

The Catalan number sequence is one of the most famous number sequences in combinatorics and is well studied in the literature. In this paper we further investigate its fundamental properties related to the moment problem and prove for the first time that it is an infinitely divisible Stieltjes moment sequence in the sense of S.-G. Tyan. Besides, any positive real power of the sequence is still a Stieltjes determinate sequence. Some more cases including (a) the central binomial coefficient sequence (related to the Catalan sequence), (b) a double factorial number sequence and (c) the generalized Catalan (or Fuss–Catalan) sequence are also investigated. Finally, we pose two conjectures including the determinacy equivalence between powers of nonnegative random variables and powers of their moment sequences, which is supported by some existing results. [ABSTRACT FROM AUTHOR]

Abstract For an abelian group G and an integer t > 0 , the modified Erdös–Ginzburg–Ziv constant s t ′ (G) is the smallest integer ℓ such that any zero-sum sequence of length at least ℓ with elements in G contains a zero-sum subsequence (not necessarily consecutive) of length t. We compute s t ′ (G) for G = Z ∕ n Z and for G = (Z ∕ n Z) 2 when t = n. [ABSTRACT FROM AUTHOR]

Abstract A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler's inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from (3 5 | 3 5) and (3 25 | 5 15). [ABSTRACT FROM AUTHOR]

Abstract Two graphs are said to be L -cospectral (respectively, Q -cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph G is said to be L − D S (respectively, Q − D S) if there does not exist other non-isomorphic graph H such that H and G are L -cospectral (respectively, Q -cospectral). Let d 1 (G) ≥ d 2 (G) ≥ ⋯ ≥ d n (G) be the degree sequence of a graph G with n vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with d 1 (G) ∈ { 4 , 5 }), if H is L -cospectral (respectively, Q -cospectral) with a connected graph G and d 2 (G) = 2 , then H has the same degree sequence as G. A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both L − D S , which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014). [ABSTRACT FROM AUTHOR]

Abstract We present a simple framework for constructing de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes four previously known de Bruijn sequence constructions and is applied to derive three new and simple de Bruijn sequence constructions. Four of the constructions apply the pure cycling register and three apply the complemented cycling register. The correctness of each new construction is easily proved using the new framework. Each of the three new de Bruijn sequence constructions can be generated in O (n) -time per bit using O (n) -space. [ABSTRACT FROM AUTHOR]

In this paper we propose a conjecture concerning partial sums of an arbitrary finite subset of an abelian group that naturally arises investigating simple Heffter systems. Then we show its connection with related open problems and we present some results about the validity of these conjectures. [ABSTRACT FROM AUTHOR]

We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called codemaker constructs a hidden sequence H = ( h 1 , h 2 , … , h n ) of colors selected from an alphabet A = { 1 , 2 , … , k } ( i.e., h i ∈ A for all i ∈ { 1 , 2 , … , n } ). The game then proceeds in turns, each of which consists of two parts: in turn t , the second player (the codebreaker ) first submits a query sequence Q t = ( q 1 , q 2 , … , q n ) with q i ∈ A for all i , and second receives feedback Δ ( Q t , H ) , where Δ is some agreed-upon function of distance between two sequences with n components. The game terminates when the codebreaker has determined the value of H , and the codebreaker seeks to end the game in as few turns as possible. Throughout we let f ( n , k ) denote the smallest integer such that the codebreaker can determine any H in f ( n , k ) turns. We prove three main results: First, when H is known to be a permutation of { 1 , 2 , … , n } , we prove that f ( n , n ) ≥ n − log log n for all sufficiently large n . Second, we show that Knuth’s Minimax algorithm identifies any H in at most n k queries. Third, when feedback is not received until all queries have been submitted, we show that f ( n , k ) = Ω ( n log k ) . [ABSTRACT FROM AUTHOR]

Let D be a finite and simple digraph with vertex set V ( D ) . For a vertex v ∈ V ( D ) , the degree d ( v ) of v is defined as the minimum value of its out-degree d + ( v ) and its in-degree d − ( v ) . If D is a graph or a digraph with minimum degree δ and edge-connectivity λ , then λ ≤ δ . A graph or a digraph is maximally edge-connected if λ = δ . A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree. In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph. [ABSTRACT FROM AUTHOR]

Suppose that H is a simple uniform hypergraph satisfying | E ( H ) | = k ( | V ( H ) | − 1 ) . A k -partition π = ( X 1 , X 2 , … , X k ) of E ( H ) such that | X i | = | V ( H ) | − 1 for 1 ≤ i ≤ k is a uniform k -partition. Let P k ( H ) be the collection of all uniform k -partitions of E ( H ) and define ε ( π ) = ∑ i = 1 k c ( H ( X i ) ) − k , where c ( H ) denotes the number of maximal partition-connected sub-hypergraphs of H . Let ε ( H ) = min π ∈ P k ( H ) ε ( π ) . Then ε ( H ) ≥ 0 with equality holds if and only if H is a union of k edge-disjoint spanning hypertrees. The parameter ε ( H ) is used to measure how close H is being from a union of k edge-disjoint spanning hypertrees. We prove that if H is a simple uniform hypergraph with | E ( H ) | = k ( | V ( H ) | − 1 ) and ε ( H ) > 0 , then there exist e ∈ E ( H ) and e ′ ∈ E ( H c ) such that ε ( H − e + e ′ ) < ε ( H ) . This generalizes a former result, which settles a conjecture of Payan. The result iteratively defines a finite ε -decreasing sequence of uniform hypergraphs H 0 , H 1 , H 2 , … , H m such that H 0 = H , H m is the union of k edge-disjoint spanning hypertrees, and such that two consecutive hypergraphs in the sequence differ by exactly one hyperedge. [ABSTRACT FROM AUTHOR]

Let G be a finite group, written multiplicatively. The Davenport constant of G is the smallest positive integer D ( G ) such that every sequence of G with D ( G ) elements has a non-empty subsequence with product 1 . Let D 2 n be the Dihedral Group of order 2 n and Q 4 n be the Dicyclic Group of order 4 n . Zhuang and Gao (2005) showed that D ( D 2 n ) = n + 1 and Bass (2007) showed that D ( Q 4 n ) = 2 n + 1 . In this paper, we give explicit characterizations of all sequences S of G such that | S | = D ( G ) − 1 and S is free of subsequences whose product is 1, where G is equal to D 2 n or Q 4 n for some n . [ABSTRACT FROM AUTHOR]

The neighborhood degree list (NDL) is a graph invariant that refines information given by the degree sequence and joint degree matrix of a graph and is useful in distinguishing graphs having the same degree sequence. We show that the space of realizations of an NDL is connected via a switching operation. We then determine the NDLs that have a unique realization by a labeled graph; the characterization ties these NDLs and their realizations to the threshold graphs and difference graphs. [ABSTRACT FROM AUTHOR]

Let N ( 2 ) and N ( 5 ) be the sets of integer solutions of 2 x 2 + y 1 2 + y 2 2 = 4 x y 1 y 2 and 5 x 2 + y 1 2 + y 2 2 = 5 x y 1 y 2 , respectively. The elements of these sets give sequences in the non-discrete part of the Markoff spectrum consisting of the normalized values of arithmetic minima of indefinite quadratic forms. Each of these sets can be represented by a bipartite graph. Using this we can construct quadratic forms giving the values of the sequences. We show that, for a quadratic form f which gives a value of the Markoff spectrum corresponding to an integer solution x of N ( 2 ) and N ( 5 ) , the roots of f ( ξ , 1 ) = 0 have a periodic continued fraction expansion and the period is a palindrome with fixed prefix and suffix on { 1 , 2 , 3 } and { 1 , 2 , 3 , 4 } , respectively. [ABSTRACT FROM AUTHOR]

We prove that the cop number of every generalized Petersen graph is at most 4. The strategy is to play a modified game of cops and robbers on an infinite cyclic covering space where the objective is to capture the robber or prevent the robber from visiting any vertex infinitely often. We also prove that finite isometric subtrees of any graph are 1-guardable, and we apply this to determine the exact cop number of some families of generalized Petersen graphs. Additionally, we extend these ideas to prove that the cop number of any connected I -graph is at most 5. [ABSTRACT FROM AUTHOR]

Let ( a 0 , a 1 , a 2 , … ) be the sequence of Catalan-like numbers. We evaluate the Hankel determinants of the shifted sequence ( 0 , a 0 , a 1 , a 2 , … ) . As an application, we settle Barry’s three conjectures about Hankel determinant evaluations of certain sequences in a unified approach. We also provide some Somos sequences by means of Hankel determinants of the (shifted) Catalan-like numbers. [ABSTRACT FROM AUTHOR]

A k -ary de Bruijn sequence of order n is a cyclic sequence of length k n in which each k -ary string of length n appears exactly once as a substring. A shift rule for a de Bruijn sequence of order n is a function that maps each length n substring to the next length n substring in the sequence. We present the first known shift rule for k -ary de Bruijn sequences that runs in O ( 1 ) -amortized time per symbol using O ( n ) space. Our rule generalizes the authors’ recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127–131). [ABSTRACT FROM AUTHOR]

A sequence over an n -element alphabet is called a k -radius sequence if any two distinct elements of the alphabet occur within distance k of each other somewhere in the sequence. Let f k ( n ) be the shortest length of a k -radius sequence over an n -element alphabet. In this note we give a new construction of “short” k -radius sequences, based on the concept of a difference family. It allows us to prove that for every fixed positive integer k there are infinitely many values of n such that f k ( n ) = 1 k n 2 + O ( n ) . This way we improve an earlier result by Blackburn and McKee (2012) who showed that the same formula holds for infinitely many values of n only when k satisfies some special conditions. [ABSTRACT FROM AUTHOR]

Analogous to MacMahon’s definition of compositions, the second author, 2000, defined n -color compositions as n -color ordered partitions. Several combinatorial properties of n -color compositions were subsequently found by him, 2003, G. Narang and A.K. Agarwal, 2006, 2008, and C. Shapcott, 2012. Recently, Y. Guo 2012, 2013, studied three restricted n -color composition functions and found generating functions, explicit formulas and recurrence relations for them. In this paper, we introduce nine new restricted n -color composition functions. It is then shown that three of them are equal to three other functions. Eventually, here we study six integer sequences from the combinatorial point of view. In addition to generating functions, explicit formulas and recurrence relations for each of them, we also obtain six combinatorial identities involving different n -color composition functions. The main results of this paper are contained in Section 3. [ABSTRACT FROM AUTHOR]

For every natural number n ≥ 2 and every finite sequence L of natural numbers, we consider the set U D n ( L ) of all uniquely decodable codes over an n -letter alphabet with the sequence L as the sequence of code word lengths, as well as its subsets P R n ( L ) and F D n ( L ) consisting of, respectively, the prefix codes and the codes with finite delay. We derive the estimation for the quotient | U D n ( L ) | ∕ | P R n ( L ) | , which allows to characterize those sequences L for which the equality P R n ( L ) = U D n ( L ) holds. We also characterize those sequences L for which the equality F D n ( L ) = U D n ( L ) holds. [ABSTRACT FROM AUTHOR]

Chung, Graham, and Wilson proved that a graph is quasirandom if and only if there is a large gap between its first and second largest eigenvalue. Recently, the authors extended this characterization to coregular k -uniform hypergraphs with loops. However, for k ≥ 3 no k -uniform hypergraph is coregular. In this paper we remove the coregular requirement. Consequently, the characterization can be applied to k -uniform hypergraphs; for example it is used in Lenz and Mubayi (2015) [5] to show that a construction of a k -uniform hypergraph sequence has some quasirandom properties. The specific statement that we prove here is that if a k -uniform hypergraph satisfies the correct count of a specially defined four-cycle, then its second largest eigenvalue is much smaller than its largest one. [ABSTRACT FROM AUTHOR]

We associate, with every infinite word over a finite alphabet, an increasing sequence of rooted finite graphs, which provide a discrete approximation of the famous Sierpiński carpet fractal. Each of these sequences converges, in the Gromov–Hausdorff topology, to an infinite rooted graph. We give an explicit description of the metric compactification of each of these limit graphs. In particular, we are able to classify Busemann and non-Busemann points of the metric boundary. It turns out that, with respect to the uniform Bernoulli measure on the set of words indexing the graphs, for almost all the infinite graphs, the boundary consists of four Busemann points and countably many non-Busemann points. [ABSTRACT FROM AUTHOR]

We study the classes of ( u , m , e , s ) -nets and ( u , e , s ) -sequences, which are generalizations of ( u , m , s ) -nets and ( u , s ) -sequences, respectively. We show equivalence results that link the existence of ( u , m , e , s ) -nets and so-called mixed (ordered) orthogonal arrays, thereby generalizing earlier results by Lawrence, and Mullen and Schmid. We use this combinatorial equivalence principle to obtain new results on the possible parameter configurations of ( u , m , e , s ) -nets and ( u , e , s ) -sequences, which generalize in particular a result of Martin and Stinson. [ABSTRACT FROM AUTHOR]

Let S = ( a 1 , … , a m ; b 1 , … , b n ) , where a 1 , … , a m and b 1 , … , b n are two nonincreasing sequences of nonnegative integers. The pair S = ( a 1 , … , a m ; b 1 , … , b n ) is said to be a bigraphic pair if there is a simple bipartite graph G = ( X ∪ Y , E ) such that a 1 , … , a m and b 1 , … , b n are the degrees of the vertices in X and Y , respectively. Let A be an (additive) Abelian group. We define σ ( A , m , n ) to be the minimum integer k such that every bigraphic pair S = ( a 1 , … , a m ; b 1 , … , b n ) with a m , b n ≥ 2 and σ ( S ) = a 1 + ⋯ + a m ≥ k has an A -connected realization. In this paper, we determine the values of σ ( Z 3 , m , m ) for m ≥ 4 . [ABSTRACT FROM AUTHOR]

Given the degree sequence d of a graph, the realization graph of d is the graph having as its vertices the labeled realizations of d , with two vertices adjacent if one realization may be obtained from the other via an edge-switching operation. We describe a connection between Cartesian products in realization graphs and the canonical decomposition of degree sequences described by R.I. Tyshkevich and others. As applications, we characterize the degree sequences whose realization graphs are triangle-free graphs or hypercubes. [ABSTRACT FROM AUTHOR]

A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph G is called a total dominating sequence if every vertex v in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes v in the sequence, and at the end all vertices of G are totally dominated. While the length of a shortest such sequence is the total domination number of G , in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, γ gr t ( G ) , of G . We provide a characterization of the graphs G for which γ gr t ( G ) = | V ( G ) | and of those for which γ gr t ( G ) = 2 . We show that if T is a nontrivial tree of order n with no vertex with two or more leaf-neighbors, then γ gr t ( T ) ≥ 2 3 ( n + 1 ) , and characterize the extremal trees. We also prove that for k ≥ 3 , if G is a connected k -regular graph of order n different from K k , k , then γ gr t ( G ) ≥ ( n + ⌈ k 2 ⌉ − 2 ) / ( k − 1 ) if G is not bipartite and γ gr t ( G ) ≥ ( n + 2 ⌈ k 2 ⌉ − 4 ) / ( k − 1 ) if G is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number. [ABSTRACT FROM AUTHOR]

We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences ( H k ) indexed by a tuple k = ( k 1 , … , k h ) of positive integers, with the property that, for each fixed graph G , there is a multivariate polynomial p ( G ; x 1 , … , x h ) such that the number of homomorphisms from G to H k is given by the evaluation p ( G ; k 1 , … , k h ) . A classical example is the sequence of complete graphs ( K k ) , for which p ( G ; x ) is the chromatic polynomial of G . Our construction is based on tree model representations of graphs. It produces a large family of graph polynomials which includes the Tutte polynomial, the Averbouch–Godlin–Makowsky polynomial, and the Tittmann–Averbouch–Makowsky polynomial. We also introduce a new graph parameter, the branching core size of a simple graph, derived from its representation under a particular tree model, and related to how many involutive automorphisms it has. We prove that a countable family of graphs of bounded branching core size is always contained in the union of a finite number of strongly polynomial sequences. [ABSTRACT FROM AUTHOR]

The de Bruijn torus (or grid) problem looks to find an n -by- m binary matrix in which every possible j -by- k submatrix appears exactly once. The existence and construction of these binary matrices were determined in the 70s, with generalizations to d -ary matrices in the 80s and 90s. However, these constructions lacked efficient decoding methods, leading to new constructions in the early 2000s. The new constructions develop cross-shaped patterns (rather than rectangular), and rely on a concept known as a half de Bruijn sequence. In this paper, we further advance this construction beyond cross-shape patterns. Furthermore, we show results for universal cycle grids, based off of the one-dimensional universal cycles introduced by Chung, Diaconis, and Graham, in the 90s. These grids have many applications such as robotic vision, location detection, and projective touch-screen displays. [ABSTRACT FROM AUTHOR]

Motivated by a problem of Knuth we consider set partitions in which every pair of elements a , b in a block satisfies | a − b | ≠ d > 0 . We explore enumeration results and combinatorial identities which arise from imposition of related distance restrictions on partitions. Our tools include elementary bijection techniques and the concept of generalized successions , that is, pairs of consecutive elements in a sequence. The underlying theme is a correspondence between successions and the cardinality of a distinguished block in a partition. As an application we obtain a new proof of a combinatorial identity found by Chu and Wei (2008). [ABSTRACT FROM AUTHOR]

Let H = ( V , E ) be an r -uniform hypergraph. For each 1 ≤ s ≤ r − 1 , an s -path P n r , s of length n in H is a sequence of distinct vertices v 1 , v 2 , … , v s + n ( r − s ) such that { v 1 + i ( r − s ) , … , v s + ( i + 1 ) ( r − s ) } ∈ E ( H ) for each 0 ≤ i ≤ n − 1 . Recently, the Ramsey number of 1-paths in uniform hypergraphs has received a lot of attention. In this paper, we consider the Ramsey number of r / 2 -paths for even r . Namely, we prove the following exact result: R ( P n r , r / 2 , P 3 r , r / 2 ) = R ( P n r , r / 2 , P 4 r , r / 2 ) = ( n + 1 ) r 2 + 1 . [ABSTRACT FROM AUTHOR]

Given a set of integers with no 3-term arithmetic progression, one constructs a Stanley sequence by choosing integers greedily without forming such a progression. This paper offers two main contributions to the theory of Stanley sequences. First, we describe all known Stanley sequences with closed-form expressions as solutions to constraints in modular arithmetic, defining the modular and pseudomodular Stanley sequences . Second, we introduce the basic Stanley sequences , whose elements arise as the sums of finite subsets of a basis sequence. Applications of our results include the construction of Stanley sequences with arbitrarily large gaps between terms, answering a weak version of a problem by Erdős et al. Finally, we generalize several results about Stanley sequences to p -free sequences, where p is any odd prime. [ABSTRACT FROM AUTHOR]

We provide sufficient conditions under which the Catalan-like numbers are Stieltjes moment sequences. As applications, we show that many well-known counting coefficients, including the Bell numbers, the Catalan numbers, the central binomial coefficients, the central Delannoy numbers, the factorial numbers, the large and little Schröder numbers, are Stieltjes moment sequences in a unified approach. [ABSTRACT FROM AUTHOR]

In pebbling problems, pebbles are placed on the vertices of a graph. A pebbling move consists of removing two pebbles from one vertex, throwing one away, and moving the other pebble to an adjacent vertex. We say a distribution D is solvable if starting from D , we can move a pebble to any vertex by a sequence of pebbling moves. The optimal pebbling number of a graph G is the smallest number of pebbles in a solvable distribution on G . It is known that every solvable distribution on the n -dimensional hypercube Q n contains at least ( 4 3 ) n pebbles. Fu, Huang, and Shiue, building on the work of Moews, used probabilistic methods to show that there are solvable distributions where the number of pebbles is in O ( ( 4 3 ) n n 3 2 ) , but hitherto, the number of pebbles in the best constructed distributions was in O ( 1.37 7 n ) . We use error-correcting codes to construct solvable distributions of pebbles on Q n in which the number of pebbles is in O ( 1.3 4 n ) . [ABSTRACT FROM AUTHOR]

A nonnegative integer n -tuple ( d 1 , … , d n ) (not necessarily monotone) is graphic if there is a simple graph G with the vertex set { v 1 , … , v n } in which the degree of v i is d i . Graphic n -tuples ( d 1 ( 1 ) , … , d n ( 1 ) ) and ( d 1 ( 2 ) , … , d n ( 2 ) ) pack if there are edge-disjoint n -vertex graphs G 1 and G 2 with the same vertex set { v 1 , … , v n } such that d G 1 ( v i ) = d i ( 1 ) and d G 2 ( v i ) = d i ( 2 ) for all i . Let Δ ( π ) and δ ( π ) denote the largest and smallest entries in n -tuple π respectively. For graphic n -tuples π 1 and π 2 , Busch et al. (2012) proved that if Δ ( π 1 + π 2 ) ≤ 2 δ ( π 1 + π 2 ) n − ( δ ( π 1 + π 2 ) − 1 ) (strict inequality when δ ( π 1 + π 2 ) = 1 ), then π 1 and π 2 pack. As a more direct analogue to the Sauer–Spencer Theorem, Busch et al. conjectured that if δ ( π 1 + π 2 ) ≥ 1 and the product of corresponding entries in π 1 and π 2 is always less than n 2 , then π 1 and π 2 pack. In this paper, we prove that if δ ( π 1 ) ≥ 1 , π 2 is an almost k -regular graphic n -tuple with k ≥ 1 , and the product of corresponding entries in π 1 and π 2 is always less than n 2 , then π 1 and π 2 pack. This is an interesting variation of Kundu’s Theorem. Combining this result with a counterexample to the above conjecture of Busch et al., we present a slight modification of this conjecture as follows: if δ ( π 1 ) ≥ 1 , δ ( π 2 ) ≥ 1 and the product of corresponding entries in π 1 and π 2 is always less than n 2 , then π 1 and π 2 pack. [ABSTRACT FROM AUTHOR]

For a finite abelian group G and a positive integer k , let s k ( G ) denote the smallest integer ℓ ∈ N such that any sequence S of elements of G of length | S | ≥ ℓ has a zero-sum subsequence with length k . The celebrated Erdős–Ginzburg–Ziv theorem determines s n ( C n ) = 2 n − 1 for cyclic groups C n , while Reiher showed in 2007 that s n ( C n 2 ) = 4 n − 3 . In this paper we prove for a p -group G with exponent exp ( G ) = q the upper bound s k q ( G ) ≤ ( k + 2 d − 2 ) q + 3 D ( G ) − 3 whenever k ≥ d , where d = ⌈ D ( G ) q ⌉ and p is a prime satisfying p ≥ 2 d + 3 ⌈ D ( G ) 2 q ⌉ − 3 , where D ( G ) is the Davenport constant of the finite abelian group G . This is the correct order of growth in both k and d . Subject to the same assumptions, we show exact equality s k q ( G ) = k q + D ( G ) − 1 if k ≥ p + d and p ≥ 4 d − 2 , resolving a case of the conjecture of Gao, Han, Peng, and Sun that s k exp ( G ) ( G ) = k exp ( G ) + D ( G ) − 1 whenever k exp ( G ) ≥ D ( G ) . We also obtain a general bound s k n ( C n d ) ≤ 9 k n for n with large prime factors and k sufficiently large. Our methods extend the algebraic method of Kubertin, who proved that s k q ( C q d ) ≤ ( k + C d 2 ) q − d if k ≥ d and q is a prime power. [ABSTRACT FROM AUTHOR]

Pick any length n binary string b 1 b 2 ⋯ b n and remove the first bit b 1 . If b 2 b 3 ⋯ b n 1 is a necklace, then append the complement of b 1 to the end of the remaining string; otherwise append b 1 . By repeating this process, eventually all 2 n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O ( 1 ) -amortized time per bit. [ABSTRACT FROM AUTHOR]

The type t G ( v ) of a vertex v ∈ V ( G ) is the ordered degree-sequence ( d 1 , … , d d G ( v ) ) of the vertices adjacent with v , where d 1 ≤ ⋯ ≤ d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ≤ a | V ( G ) | + b holds is finite when a ≤ 1 and infinite when a ≥ 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a function of the number of vertices. In addition we prove that the lexicographic product of two graphs is vertex-oblique if and only if both of its factors are vertex-oblique. [ABSTRACT FROM AUTHOR]

A triple of vertices in a graph is a frustrated triangle if it induces an odd number of edges. We study the set F n ⊂ [ 0 , ( n 3 ) ] of possible number of frustrated triangles f ( G ) in a graph G on n vertices. We prove that about two thirds of the numbers in [ 0 , n 3 / 2 ] cannot appear in F n , and we characterise the graphs G with f ( G ) ∈ [ 0 , n 3 / 2 ] . More precisely, our main result is that, for each n ≥ 3 , F n contains two interlacing sequences 0 = a 0 ≤ b 0 ≤ a 1 ≤ b 1 ≤ ⋯ ≤ a m ≤ b m ∼ n 3 / 2 such that F n ∩ ( b t , a t + 1 ) = 0̸ for all t , where the gaps are | b t − a t + 1 | = ( n − 2 ) − t ( t + 1 ) and | a t − b t | = t ( t − 1 ) . Moreover, f ( G ) ∈ [ a t , b t ] if and only if G can be obtained from a complete bipartite graph by flipping exactly t edges/nonedges. On the other hand, we show, for all n sufficiently large, that if m ∈ [ f ( n ) , ( n 3 ) − f ( n ) ] , then m ∈ F n where f ( n ) is asymptotically best possible with f ( n ) ∼ n 3 / 2 for n even and f ( n ) ∼ 2 n 3 / 2 for n odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with n vertices and e ≤ n 2 / 4 edges. [ABSTRACT FROM AUTHOR]

In this paper we prove the strong q -log-convexity of the Eulerian polynomials of Coxeter groups using their exponential generating functions. Our proof is based on the theory of exponential Riordan arrays and a criterion for determining the strong q -log-convexity of polynomial sequences, whose generating functions can be given by a continued fraction. As applications, we get the strong q -log-convexity of the Eulerian polynomials of types A n , B n , their q -analogue and the generalized Eulerian polynomials associated to the arithmetic progression { a , a + d , a + 2 d , a + 3 d , … } in a unified manner. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of avoidance of subword patterns in flattened partitions, which extends recent work of Callan. We determine in all cases explicit formulas and/or generating functions for the number of set partitions of size n which avoid a single subword pattern of length three. The asymptotic behavior of the resulting counting sequences turns out to depend quite heavily on the specific pattern. For the cases of 312 and 213, we make use of the kernel method to determine the generating function which counts the members of the avoidance class. Furthermore, in the cases of 132, 231, and 123, we also find formulas concerning the distribution on the set of partitions for the statistics recording the number of occurrences of the pattern in question and some related bijective proofs are given. Finally, in each of these cases, it is shown that the number of occurrences of the pattern asymptotically follows a normal distribution. [ABSTRACT FROM AUTHOR]

From an initial list of nonnegative integers, we form a Stanley sequence by recursively adding the smallest integer such that the list remains increasing and no three elements form an arithmetic progression. Odlyzko and Stanley conjectured that every Stanley sequence ( a n ) satisfies one of two patterns of asymptotic growth, with no intermediate behavior possible. Sequences of Type 1 satisfy α / 2 ≤ lim inf n → ∞ a n / n log 2 3 ≤ lim sup n → ∞ a n / n log 2 3 ≤ α , for some constant α , while those of Type 2 satisfy a n = Θ ( n 2 / log n ) . In this paper, we consider the possible values for α in the growth of Type 1 Stanley sequences. Whereas Odlyzko and Stanley considered only those Type 1 sequences for which α equals 1, we show that α can in fact be any rational number that is at least 1 and for which the denominator, in lowest terms, is a power of 3. [ABSTRACT FROM AUTHOR]

The central coefficients of powers of certain polynomials with arbitrary degree in x form an important family of integer sequences. Although various recursive equations addressing these coefficients do exist, no explicit analytic representation has yet been proposed. In this article, we present an explicit form of the integer sequences of central multinomial coefficients of polynomials of even degree in terms of finite sums over Dirichlet kernels, hence linking these sequences to discrete n th-degree Fourier series expansions. The approach utilizes the diagonalization of circulant Boolean matrices, and is generalizable to all multinomial coefficients of certain polynomials with even degree, thus forming the base for a new family of combinatorial identities. [ABSTRACT FROM AUTHOR]

Given a set F of graphs, a graph G is F -free if G does not contain any member of F as an induced subgraph. A set F is degree-sequence-forcing (DSF) if, for each graph G in the class C of F -free graphs, every realization of the degree sequence of G is also in C . A DSF set is minimal if no proper subset is also DSF. In this paper, we present new properties of minimal DSF sets, including that every graph is in a minimal DSF set and that there are only finitely many DSF sets of cardinality k . Using these properties and a computer search, we characterize the minimal DSF triples. [ABSTRACT FROM AUTHOR]

In a recent work of Savage and Viswanathan (2012), during studies of the set of n -dimensional k -inversion sequences, the so-called 1 / k -Eulerian polynomials have been introduced, which are given as generating polynomials of the number of ascents in such inversion sequences. In this paper, we discover that the 1 / k -polynomials are also generating polynomials of the number of the longest ascent plateaus of k -Stirling permutations. Moreover, we also introduce the dual set of Stirling permutations. [ABSTRACT FROM AUTHOR]

We describe a class of Skolem sequences of order n such that for the cyclic Steiner triple system of order 6 n + 1 generated by any Skolem sequence from the class we can construct a bipartite index one current graph generating a nonorientable face 2-colorable triangular embedding of the complete graph K 6 n + 1 such that the triangular faces of one of the two color classes form the blocks of the cyclic Steiner triple system. [ABSTRACT FROM AUTHOR]

For a finite sequence of positive integers to be the degree sequence of a finite graph, Zverovich and Zverovich gave a sufficient condition involving only the length of the sequence, its largest entry and its smallest entry. Barrus, Hartke, Jao, and West gave a better bound and showed that the sharp bound is never less than theirs by more than 1. In this paper we determine the sharp bound. [ABSTRACT FROM AUTHOR]

A universal traversal sequence for the family of all connected d -regular graphs of order n with an edge-labeling is a sequence of { 0 , 1 , … , d − 1 } ∗ that traverses every graph of the family starting at every vertex of the graph. Reflecting sequences are variants of universal traversal sequences. A t -reflecting sequence for the family of all labeled chains of length n is a sequence of { 0 , 1 } ∗ that alternately visits the end-vertices and reflects at least t times in every labeled chain of the family. We present an algorithm for finding lower bounds on the lengths of reflecting sequences for labeled chains. Using the algorithm, we show a length lower bound of 19 t − 214 for t -reflecting sequences for labeled chains of length 7, which yields the length lower bounds of Ω ( n 1.51 ) and Ω ( d 0.49 n 2.51 ) for universal traversal sequences for 2- and d -regular graphs, respectively, of n vertices, where 3 ≤ d ≤ n 17 + 1 . [ABSTRACT FROM AUTHOR]

In Bryant et al. (1996) it is shown that there exists a 5-cycle system of K v + u − K v if and only if the obvious necessary conditions are satisfied. One purpose of this paper is to extend this result by providing the necessary and sufficient conditions for the existence of a 5-cycle system of λ K v + u − λ K v . It was shown in Asplund et al. (2013) that if there exists a 5-cycle system of λ K v , then there exists a 5-cycle system of ( λ + m ) K v + 1 − λ K v if and only if v is ( λ , 5 ) -admissible. The second purpose of this paper is to extend this result by removing the requirement that there exists a 5-cycle system of λ K v . In doing so, we will show that there exists a 5-cycle system of ( λ + m ) K v + 1 − λ K v if and only if the obvious necessary conditions are satisfied, except possibly in two cases. [ABSTRACT FROM AUTHOR]

Given a sequence of n nonnegative integers how can we find the graphs which achieve the minimal deviation from that sequence? This extends the classical problem regarding what sequences are “graphic”, that is, can be the degrees of a simple graph, to issues regarding arbitrary sequences. In this context, we investigate properties of the “minimal graphs”. We shall demonstrate how a variation on the Havel–Hakimi algorithm can supply the value of the minimal possible deviation, and how consideration of the Ruch–Gutman condition and the Ferrer diagram can yield the complete set of graphs achieving this minimum. An application of this analysis is to a population of individuals represented by vertices, interactions between pairs by edges and in which each individual has a preferred range for their number of links to other individuals. Individuals adjust their links according to their preferred range and the graph evolves towards some set of graphs which achieve the minimal possible deviation. This Markov chain is defined but detailed analysis is omitted. [ABSTRACT FROM AUTHOR]

For a given positive integer N , and any coloring function c : N → { 0 , 1 } satisfying c ( 2 k ) = 1 − c ( k ) , c ( 2 k + 1 ) = c ( k ) for all k ≥ N , we show that for all n ≥ 20 N , n has both a monochromatic representation and a multicolored representation, in other words, there exist x , y , u , v ∈ N , such that n = x + y = u + v , c ( x ) = c ( y ) and c ( u ) ≠ c ( v ) . Similar results are obtained for another kind of coloring function c : N → { 0 , 1 } satisfying c ( 2 k ) = c ( k ) and c ( 2 k + 1 ) = 1 − c ( k ) for all k ≥ N . This answers a question of Y.-G. Chen on the values of representation functions. [ABSTRACT FROM AUTHOR]

We study the bounded regions in a generic slice of the hyperplane arrangement in R n consisting of the hyperplanes defined by x i and x i + x j . The bounded regions are in bijection with several classes of combinatorial objects, including the ordered partitions of [ n ] all of whose left-to-right minima occur at odd locations and the drawings of rooted plane trees with n + 1 vertices. These are sequences of rooted plane trees such that each tree in a sequence can be obtained from the next one by removing a leaf. [ABSTRACT FROM AUTHOR]

An N -ary plane multitree is a rooted tree whose subtrees at any vertex are linearly ordered, and every node has at most N outgoing edges to its children, and two nodes can be connected by multiple edges. An N -Raney path of length n is a lattice path running from ( 0 , 1 ) to ( n , 0 ) consisting of steps ( 1 , k ) for k ∈ Z such that k ≤ N , and for which all points except the last one lie above the x -axis. We show a bijection between N -Raney paths of length n and ( N + 1 ) -ary plane multitrees of n nodes. We show also a bijection between Raney paths and Raney sequences of integers whose sum is + 1 and every partial sum is positive. These two bijections are a main tool to derive formulas for the number of N -ary plane multitrees with specified number of nodes, edges, and leaves. Some statistical properties are considered. It is shown that when N and n tend to infinity, the ratio of the number of leaves to the total number of nodes in all N -ary plane multitrees with n nodes is 1 / e . [ABSTRACT FROM AUTHOR]