Search

This paper provides a necessary and sufficient condition for resolving sets to have exchange property in the power graph of a finite group. As its application, the paper shows that the resolving sets do not have exchange property in the power graph of the symmetric group S n if and only if n = 2 + p where p is a prime with p > 3 .

In this article we prove bounds for the boundary length of patches with a given set of bounded faces. We assume that with t the number of given triangles, q the number of quadrangles, and p the number of pentagons, the curvature 3 t + 2 q + p is at most 6 and that at an interior vertex exactly 3 faces meet. We prove that one gets a patch with shortest boundary if one arranges the faces in a spiral order and with increasing size. Furthermore we give explicit formulas that allow to determine all boundary lengths that occur for patches with given numbers p , q and t 2 and no bounded face larger than 6. The patches studied in this article occur as subgraphs of 3-regular graphs in mathematics as well as models for planar polycyclic hydrocarbons in chemistry where the bounds allow to decide on the (theoretical) existence of molecules for a given chemical formula.

We define a tournament to be alternation acyclic if it does not contain a cycle in which descents and ascents alternate. Using a result by Athanasiadis on hyperplane arrangements, we show that these tournaments are counted by the median Genocchi numbers. By establishing a bijection with objects defined by Dumont, we show that alternation acyclic tournaments in which at least one ascent begins at each vertex, except for the largest one, are counted by the Genocchi numbers of the first kind. Unexpected consequences of our results include a pair of ordinary generating function formulas for the Genocchi numbers of both kinds and a new very simple model for the normalized median Genocchi numbers., Comment: Minor but important corrections. This paper has been accepted by the European Journal of Combinatorics

In this work, we first present new bijections for the composition analogues of the partition theorems of Euler, Glaisher, and Franklin respectively. Then we generalize one composition analogue of Beck’s conjectures found by Huang recently, and give a purely combinatorial proof applying our bijection. Finally, a new and general composition analogue of Beck’s conjectures is established.

We apply the homomorphism complex construction to partially ordered sets, introducing a new topological construction based on the set of maximal chains in a graded poset. Our primary objects of study are distributive lattices, with special emphasis on finite products of chains. For the special case of a Boolean algebra, we observe that the corresponding homomorphism complex is isomorphic to the subcomplex of cubical cells in a permutahedron. Thus, this work can be interpreted as a generalization of the study of these complexes. We provide a detailed investigation when our poset is a product of chains, in which case we find an optimal discrete Morse matching and prove that the corresponding complex is torsion-free., Comment: the first version was missing a statement that Kozlov defined the general hom complex construction

We classify all recurrent configurations of the Abelian sandpile model (ASM) on Ferrers graphs. The classification is in terms of decorations of EW-tableaux, which undecorated are in bijection with the minimal recurrent configurations. We introduce decorated permutations, extending to decorated EW-tableaux a bijection between such tableaux and permutations, giving a direct bijection between the decorated permutations and all recurrent configurations of the ASM. We also describe a bijection between the decorated permutations and the intransitive trees of Postnikov, the breadth-first search of which corresponds to a canonical toppling of the corresponding configurations.

In the parlance of relational structures, the Finite Ramsey Theorem states that the class of all finite chains has the Ramsey property. A classical result of J. Ne\v{s}et\v{r}il and V. R\"{o}dl claims that the class of all finite posets with a linear extension has the Ramsey property. In 2010 M. Soki\'{c} proved that the class of all finite structures consisting of several linear orders has the Ramsey property. This was followed by a 2017 result of S. Solecki and M. Zhao that the class of all finite posets with several linear extensions has the Ramsey property. Using the categorical reinterpretation of the Ramsey property in this paper we prove a common generalization of all these results. We consider multiposets to be structures consisting of several partial orders and several linear orders. We allow partial orders to extend each other in an arbitrary but fixed way, and require that every partial order is extended by at least one of the linear orders. We then show that the class of all finite multiposets conforming to a fixed template has the Ramsey property., Comment: arXiv admin note: text overlap with arXiv:1702.06596

We consider a stack sorting algorithm where only the appropriate output values are popped from the stack and then any remaining entries in the stack are run through the stack in reverse order. We identify the basis for the 2-reverse pass sortable permutations and give computational results for some classes with larger maximal rev-tier. We also show all classes of ( t + 1 ) -reverse pass sortable permutations are finitely based. Additionally, a new Entringer family consisting of maximal rev-tier permutations of length n was discovered along with a bijection between this family and the collection of alternating permutations of length n − 1 . We calculate generating functions for the number permutations of length n and exact rev-tier t .

We prove the Schröder case, i.e. the case 〈⋅,e n−d h d 〉, of the conjecture of Haglund et al. (2018) for Δ h m Δ e n−k−1 ′ e n in terms of decorated partially labelled Dyck paths, which we call generalized Delta conjecture. This result extends the Schröder case of the Delta conjecture proved in (D'Adderio, 2017), which in turn generalized the q,t-Schröder in Haglund (2004). The proof gives a recursion for these polynomials that extends the ones known for the aforementioned special cases. Also, we give another combinatorial interpretation of the same polynomial in terms of a new bounce statistic. Moreover, we give two more interpretations of the same polynomial in terms of doubly decorated parallelogram polyominoes, extending some of the results in D'Adderio (2017), which in turn extended results in Aval et al. (2014). Also, we provide combinatorial bijections explaining some of the equivalences among these interpretations., SCOPUS: ar.j, info:eu-repo/semantics/published

In the Boolean lattice, Sperner’s, Erdős’s, Kleitman’s and Samotij’s theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of Z 2 n we work in Z 2 n , several analogous statements hold if one replaces the word k -chain by projective cube of dimension 2 k − 1 . We say that B d is a projective cube of dimension d if there are numbers a 1 , a 2 , … , a d such that B d = ∑ i ∈ I a i | ∅ ≠ I ⊆ [ d ] . As an analog of Sperner’s and Erdős’s theorems, we show that whenever d = 2 l is a power of two, the largest d -cube free set in Z 2 n is the union of the largest l layers. As an analog of Kleitman’s theorem, Samotij and Sudakov asked whether among subsets of Z 2 n of given size M , the sets that minimise the number of Schur triples (2-cubes) are those that are obtained by filling up the largest layers consecutively. We prove the first non-trivial case where M = 2 n − 1 + 1 , and conjecture that the analog of Samotij’s theorem also holds. Several open questions and conjectures are also given.

An orthogonal representation of a graph is an assignment of nonzero real vectors to its vertices such that distinct non-adjacent vertices are assigned to orthogonal vectors. We prove general lower bounds on the dimension of orthogonal representations of graphs using the Borsuk-Ulam theorem from algebraic topology. Our bounds strengthen the Kneser conjecture, proved by Lov\'asz in 1978, and some of its extensions due to B\'ar\'any, Schrijver, Dol'nikov, and Kriz. As applications, we determine the integrality gap of fractional upper bounds on the Shannon capacity of graphs and the quantum one-round communication complexity of certain promise equality problems., Comment: 18 pages

For a prime power q and a positive integer n , we say a subspace U of F q n is cyclically covering if the union of the cyclic shifts of U is equal to F q n . We investigate the problem of determining the minimum possible dimension of a cyclically covering subspace of F q n . (This is a natural generalisation of a problem posed in 1991 by the first author.) We prove several upper and lower bounds, and for each fixed q , we answer the question completely for infinitely many values of n (which take the form of certain geometric series). Our results imply lower bounds for a well-known conjecture of Isbell, and a generalisation thereof, supplementing lower bounds due to Spiga. We also consider the analogous problem for general representations of groups. We use arguments from combinatorics, representation theory and finite field theory.

The concept of t -bonded sets is a generalization of the concept of Delone ( r ; R ) -system and a good instrument to create a point set model to describe materials like zeolites, which atomic structures are multi-regular “microporous” point sets. To better describe “microporous” structures it is worthwhile to take into consideration a parameter that represents atomic bonds within the matter. In this paper we generalize for t -bonded systems in R 3 results of the local theory for regular point systems previously proven for Delone ( r , R ) -systems in R 3 . Applying similar concepts and techniques the corresponding results that are proven for multi-regular ( r , R ) -systems could also be generalized for multi-regular t -bonded systems.

For a connected amply regular graph with parameters ( v , k , λ , μ ) satisfying λ ≤ μ , it is known that its diameter is bounded by k . This was generalized by Terwilliger to ( s , c , a , k ) -graphs satisfying c ≥ max { a , 2 } . It follows from Terwilliger that a connected amply regular graph with parameters ( v , k , λ , μ ) satisfying μ > k 3 ≥ 1 and μ ≥ λ has diameter at most 7. In this paper we will classify the 2-walk-regular graphs with valency k ≥ 3 and diameter at least 4 such that its intersection number c 2 satisfies c 2 > k 3 . This result generalizes a result of Koolen and Park for distance-regular graphs. And we show that if such a 2-walk-regular graph is not distance-regular, then it is the incidence graph of a group divisible design with the dual property with parameters ( 2 , m ; k ; 0 , λ 2 ) .

Plateaued and bent functions play a significant role in cryptography, sequence theory, coding theory and combinatorics. In 1997, Coulter and Matthews redefined bent functions over any finite field F q where q is a prime power, and established their properties. The objective of this work is to redefine the notion of plateaued functions over F q , and to present several explicit characterizations of those functions. We first give, over F q , the notion of q -ary plateaued functions, which relies on the concept of the Walsh–Hadamard transform in terms of canonical additive character of F q . We then give a concrete example of q -ary plateaued function, that is not vectorial p -ary plateaued function. This suggests that the study of plateaued-ness is also significant for q -ary functions over F q . We finally characterize q -ary plateaued functions in terms of derivatives, Walsh power moments and autocorrelation functions.

An envelope is equivalent to a rectangle dihedron or a doubly-covered rectangle. It is cut along a tree graph that spans the four corners of the envelope to get a planar region. We show in Theorem 1 that every region satisfies the Conway criterion and so copies of the region tile the plane using only translations and 180° rotations. Let P 1 and P 2 be two regions obtained by unfolding the same envelope along two non-crossing trees, respectively. Then we show in Theorem 2 that P 1 is equi-rotational into P 2 , which means that P 1 can be dissected into pieces that are hinged at corners, so that the pieces can be rigidly transformed into P 2 by monotonous rotations at the hinges. In Theorem 3 , Theorem 4 , we give the sufficient conditions for Conway tiles to be foldable into envelopes.

A connected graph G is called l 1 -embeddable, if G can be isometrically embedded into the l 1 -space. We prove that an l 1 -embeddable quadrilateral Mobius map ( M , G ) contains a unique shortest non-nulhomotopic cycle C , provided that ( M , G ) is generic, that is, its face cycles are isometric. Moreover, C is convex and orientation-reversing. After cutting ( M , G ) along C , the map falls apart into a number of quadrilateral plane maps called beads. We analyze the structure of the bead graph in which two beads are adjacent when they share a segment of C . We also introduce the foundation B ( M , G ) which helps to decide whether a concrete map ( M , G ) is l 1 -embeddable.

A factor (near-factor) of a finite simple graph G is a matching that saturates all vertices (except one). For m ⩾ 0 , a graph G is said to be m -critical ( m -near-critical) if the deletion of any m vertices from G produces a subgraph that has a factor (near-factor). An m -critical graph is ( m + 1 ) -near-critical. The following results are established. (i) Within the class of ( m + 1 ) -near-critical graphs, a characterization is given for those that are not m -critical. (ii) For an ( m + 1 ) -connected graph, it is ( m + 1 ) -near-critical if and only if it is m -critical. (iii) An ( m + 2 ) -near-critical graph is m -near-critical if its order is at least m + 5 .

If a planar lattice contains the vertices of a convex equilateral n -gon for some n ≠ 4 , then the lattice is similar to a sublattice of Z 5 in R 5 , and it contains the vertices of a convex equilateral 2 n -gon for every n ≥ 2 . If a planar lattice contains the vertices of an equilateral triangle, then the lattice is similar to a sublattice of Z 3 in R 3 , and it contains the vertices of a convex equilateral n -gon for every n ≥ 3 .

Let T = T ( x 0 ) be the Terwilliger algebra of the Johnson scheme J ( N , D ) , where x 0 is a fixed base point. In Liang et al. (2017), an observation is made on the parameters of Leonard systems that arise from the irreducible representations of T . This paper accounts for the observation from the viewpoint of group representations. In particular, it is shown that T is isomorphic to the centralizer algebra for the stabilizer of the base point x 0 in the automorphism group of J ( N , D ) .

International audience; The Niemeier lattices are the 23 unimodular even lattices of norm 2 in dimension 24. We determine computationally their covering radius for 16 of those lattices and give lower bounds for the remaining that we conjecture to be exact. This is achieved by computing the list of Delaunay polytopes of those lattices.

Let F be a family of sets in R d . A set M ⊂ R d is called F -convex if for any pair of distinct points x , y ∈ M , there is a set F ∈ F such that x , y ∈ F and F ⊂ M . A family F of compact sets is called complete if F contains all compact F -convex sets. Generalizing the definition in Yuan and Zamfirescu (2016), a compact set K will be called selfish, if the family F K of all sets similar to K contains all compact F K -convex sets. In this paper, we investigate the selfishness of rectangles, isosceles triangles, regular n -gons, and some finite sets.

We consider maximum properly edge-colored trees in edge-colored graphs. We also consider the problem where, given a vertex r , determine whether the graph has a spanning tree rooted at r , such that all root-to-leaf paths are properly colored. We consider these problems from graph-theoretic as well as algorithmic viewpoints. We prove their optimization versions to be NP-hard in general and provide algorithms for graphs without properly edge-colored cycles. We also derive some nonapproximability bounds. A study of the trends random graphs display with regard to the presence of properly edge-colored spanning trees is presented.

A non-empty k -regular graph Γ on n vertices is called a Deza graph if there exist constants b and a ( b ≥ a ) such that any pair of distinct vertices of Γ has either b or a common neighbours. The quantities n , k , b , and a are called the parameters of Γ and are written as the quadruple ( n , k , b , a ) . If a Deza graph has diameter 2 and is not strongly regular, then it is called a strictly Deza graph. In the present paper, we investigate strictly Deza graphs whose parameters ( n , k , b , a ) satisfy the conditions k = b + 1 and k ( k − 1 ) − a ( n − 1 ) b − a > 1 .

An embedded graph is called z -knotted if it contains a unique zigzag (up to reversing). We consider z -knotted triangulations, i.e. z -knotted embedded graphs whose faces are triangles, and describe all cases when the connected sum of two z -knotted triangulations is z -knotted.

In 1981, J. Borsik and J. Dobos analyzed what properties a function must satisfy in order to merge a collection of metric spaces into a single one. Later on, E. Castineira, A. Pradera and E. Trillas studied a variant of the same problem in which each metric of the collection to be merged is defined on the same non-empty set. In this, paper we continue the work in this last aforesaid direction. On the one hand, we provide a new characterization of such functions and a few methods to construct them. On the other hand, we analyze the existence of absorbent, idempotent and neutral elements for such class of functions and, thus, we design techniques that allow to discard those functions that are not useful for merging metrics. Finally, we discuss when the functions under study preserve metrics.

Optimal Connections Problem in the Gromov–Hausdorff space of metric compacta is investigated. To study Gromov–Hausdorff distances the technique of irreducible correspondences and relations with the finite-dimensional space with max -norm are used. As a result it is shown that the Steiner and the Gromov–Steiner ratios of the Gromov–Hausdorff space are equal to 1 ∕ 2 , but the Steiner subratio is less than 1. Moreover, a smaller estimate for the Steiner subratio is obtained.

Each nontrivial shell (i.e., subconstituent) of the Johnson association scheme J ( v , k ) is known to be a commutative association scheme which is the product of two smaller Johnson association schemes. The concept of t -designs in one shell of J ( v , k ) was naturally defined and studied by Martin in the context of mixed t -designs. The purpose of this paper is to try to push this study a bit further. First we give a direct proof of the theorem that if ( Y , w ) is a relative t -design in J ( v , k ) on p shells then the part in each shell must be a weighted ( t − p + 1 ) -design in the shell. In particular, it is a mixed ( t − p + 1 ) -design in one shell if the weight function is constant on each shell. We also present another approach that makes use of the Terwilliger algebra, based on the work of Tanaka. This result is essentially proved by Martin in 1998, but the proof there contains a small gap which is repaired in this paper. We also study the existence problems of tight 2-, 3- and 4-designs on one shell of Johnson association scheme J ( v , k ) with small parameters, say v ≤ 1000 , thereby expanding the range of search in the original paper of Martin in 1998.

For each tree T on n vertices, a labelling of T is a bijective map from the vertex set of T to the first n positive integers. We consider two maps, which send the labellings of T to labellings of T for all trees T . We show that the transformation monoid generated by these two maps has exactly five elements and we analyse the dynamical behaviours of the action of this monoid on the set of labellings of trees.

Let K be an extension of the field Q p of p -adic rationals, let O K be its ring of integers, and let G be a finite group. According to the classical Jordan–Zassenhaus Theorem, if K ∕ Q p is finite, every isomorphism class of K G -representation modules splits in a finite number of isomorphism classes of O K G -representation modules. We consider a p -group G of a given nilpotency class k > 1 and the extension K ∕ Q p where K = Q p ( ζ p ∞ ) obtained by adjoining all roots ζ p i , i = 1 , 2 , 3 , . . . of unity, and we use an explicit combinatorial construction of a faithful absolutely irreducible K G -module M to show that the number of O K G -isomorphism classes of O K G -representation modules, which are K G -equivalent to M , is infinite, and there are extra congruence properties for these O K G -modules.

Every graph G can be embedded in a Euclidean space as a two-distance set. The Euclidean representation number of G is the smallest dimension in which G is representable by such an embedding. We consider spherical and J-spherical representation numbers of G and give exact formulas for these numbers using multiplicities of polynomials that are defined by the Caley-Menger determinant. One of the main results of the paper are explicit formulas for the representation numbers of the join of graphs which are obtained from W. Kuperberg's type theorem for two-distance sets., 20 pages

We show that a weaker version of the well-known theorem of Morlaye and Joly on diagonal equations is a simple consequence of a restricted variable version of the Chevalley-Warning theorem. Moreover, we extend the result of Morlaye and Joly to the case of an equation of the form $$b_1D_{m_1}(X_1,a_1)+\dots+b_nD_{m_n}(X_n,a_n)=c,$$ where $D_{m_1}(X_1,a_1),\dots,D_{m_n}(X_n,a_n)$ are Dickson polynomials., 7 pages; Example 1 and reference [5] added

A generalized quadrangle is a point-line incidence geometry such that any two points lie on at most one line and, given a line $\ell$ and a point $P$ not incident with $\ell$, there is a unique point of $\ell$ collinear with $P$. We study the structure of groups acting regularly on the point set of a generalized quadrangle. In particular, we provide a characterization of the generalized quadrangles with a group of automorphisms acting regularly on both the point set and the line set and show that such a thick generalized quadrangle does not admit a polarity. Moreover, we prove that a group $G$ acting regularly on the point set of a generalized quadrangle of order $(u^2, u^3)$ or $(s,s)$, where $s$ is odd and $s+1$ is coprime to $3$, cannot have any nonabelian minimal normal subgroups., Comment: 16 pages; to appear in European Journal of Combinatorics

With a main tool is signed graphs, we give a full description of the characteristic quasi-polynomials of ideals of classical root systems ($ABCD$) with respect to the integer and root lattices. As a result, we obtain a full description of the characteristic polynomials of the toric arrangements defined by these ideals. As an application, we provide a combinatorial verification to the fact that the characteristic polynomial of every ideal subarrangement factors over the dual partition of the ideal in the classical cases., Comment: 17 pages, we welcome comments

In the literature, the theory of cocyclic Hadamard matrices has always been developed over finite groups. This paper introduces the natural generalization of this theory to be developed over Latin rectangles. In this regard, once we introduce the concept of binary cocycle over a given Latin rectangle, we expose examples of Hadamard matrices that are not cocyclic over finite groups but they are over Latin rectangles. Since it is also shown that not every Hadamard matrix is cocyclic over a Latin rectangle, we focus on answering both problems of existence of Hadamard matrices that are cocyclic over a given Latin rectangle and also its reciprocal, that is, the existence of Latin rectangles over which a given Hadamard matrix is cocyclic. We prove in particular that every Latin square over which a Hadamard matrix is cocyclic must be the multiplication table of a loop (not necessarily associative). Besides, we prove the existence of cocyclic Hadamard matrices over non-associative loops of order 2 t + 3 , for all positive integer t > 0 .

An r -regular family F of permutations on a set V contains, for each pair of vertices u , v ∈ V , exactly r permutations φ mapping u to v . Earlier, 1-regular families of graph automorphisms were used by Gauyacq to define the quasi-Cayley graphs, a class of vertex-transitive graphs that properly contains the class of Cayley graphs, sharing many of their characteristics, and is properly contained in the class of vertex-transitive graphs. We introduce r -regular families to measure how far a vertex-transitive graph is from being quasi-Cayley. As any automorphism group of a graph Γ = ( V , E ) acting transitively on V with vertex-stabilizers of order r forms an r -regular family on V , every vertex-transitive graph admits an r -regular family of automorphisms for some r ≥ 1 . In general, the smallest r for which such a family exists (which we call the quasi-Cayley deficiency of the graph) might be smaller than the order of the vertex-stabilizer of a smallest vertex-transitive automorphism group of the graph (which we call the Cayley deficiency). We investigate the relations between these two parameters for the class of merged Johnson graphs. We prove the existence of Johnson graphs with arbitrarily large quasi-Cayley deficiency, as well as Johnson graphs for which the difference between their Cayley deficiency and their quasi-Cayley deficiency is arbitrarily large.

Nested matroids were introduced by Crapo in 1965 and have appeared frequently in the literature since then. A flat of a matroid $M$ is Hamiltonian if it has a spanning circuit. A matroid $M$ is nested if and only if its Hamiltonian flats form a chain under inclusion; $M$ is laminar if and only if, for every $1$-element independent set $X$, the Hamiltonian flats of $M$ containing $X$ form a chain under inclusion. We generalize these notions to define the classes of $k$-closure-laminar and $k$-laminar matroids. This paper focuses on structural properties of these classes noting that, while the second class is always minor-closed, the first is if and only if $k \le 3$. The main results are excluded-minor characterizations for the classes of 2-laminar and 2-closure-laminar matroids., 12 pages

By a theorem of Drisko, any $2n-1$ matchings of size $n$ in a bipartite graph have a partial rainbow matching of size $n$. Inspired by discussion of Bar\'at, Gy\'arf\'as and S\'ark\"ozy, we conjecture that if $n$ is odd then the same is true also in general graphs, and that if $n$ is even then $2n$ matchings of size $n$ suffice. We prove that any $3n-2$ matchings of size $n$ have a partial rainbow matching of size $n$., Comment: 6 pages

We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed that every properly edge-colored complete graph $G$ on $n$ vertices has a rainbow cycle on at least $n - O(n^{3/4})$ vertices, by showing that $G$ has a rainbow cycle on at least $n - O(\log n \sqrt{n})$ vertices. Second, by modifying the argument of Hatami and Shor which gives a lower bound for the length of a partial transversal in a Latin Square, we prove that every properly colored complete graph has a Hamilton cycle in which at least $n - O((\log n)^2)$ different colors appear. For large $n$, this is an improvement of the previous best known lower bound of $n - \sqrt{2n}$ of Andersen., Comment: 12 pages

We suggest a new method for coloring generalized Kneser graphs based on hypergraphs with high discrepancy and a small number of edges. The main result provides a proper coloring of K ( n , n ∕ 2 − t , s ) in ( 4 + o ( 1 ) ) ( s + t ) 2 colors, which is produced by Hadamard matrices. Also, we show that for colorings by independent set of a natural type, this result is the best possible up to a multiplicative constant. Our method extends to Kneser hypergraphs as well.

We consider Niho bent functions (they are equivalent to bent functions which are linear on the elements of a Desarguesian spread). Niho bent functions are in one-to-one correspondence with line ovals in an affine plane. Furthermore, Niho bent functions are in one-to-one correspondence with ovals (in a projective plane) with nucleus at a designated point. We introduce a new analog of o-polynomials for description of hyperovals and present a criteria for existence of such polynomials. These connections allow us to present new simple descriptions of the Adelaide and Subiaco hyperovals and their automorphism groups. There are notions of duality for bent functions and for projective planes, we show that these notions are consistent for Niho bent functions.

Let B 1 , B 2 , … , B m be nonempty finite subsets of R d with B i not contained in an affine hyperplane for each i ∈ { 2 , 3 , … , m } . In this paper we find a nontrivial lower bound of | B 1 + B 2 + … + B m | . As a consequence of this result, a problem by M. Matolcsi and I. Z. Ruzsa is also solved.

Recently, Nunge studied Eulerian polynomials on segmented permutations, namely \emph{generalized Eulerian polynomials}, and further asked whether their coefficients form unimodal sequences. In this paper, we prove the stability of the generalized Eulerian polynomials and hence confirm Nunge's conjecture. Our proof is based on Br\"and\'en's stable multivariate Eulerian polynomials. By acting on Br\"and\'en's polynomials with a stability-preserving linear operator, we get a multivariate refinement of the generalized Eulerian polynomials. To prove Nunge's conjecture, we also develop a general approach to obtain generalized Sturm sequences from bivariate stable polynomials., Comment: to appear in European Journal of Combinatorics

Let [ R n , k ] n , k ≥ 0 be an array of nonnegative numbers satisfying the recurrence relation R n , k = ( a 1 n + a 2 k + a 3 ) R n − 1 , k + ( b 1 n + b 2 k + b 3 ) R n − 1 , k − 1 + ( c 1 n + c 2 k + c 3 ) R n − 1 , k − 2 with R 0 , 0 = 1 and R n , k = 0 unless 0 ≤ k ≤ n . In this paper, we first prove that the array [ R n , k ] n , k ≥ 0 can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of [ R n , k ] n , k ≥ 0 . Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type B , and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong q -log-convexity of some generating functions.

Baker and Norine proved a Riemann--Roch theorem for divisors on undirected graphs. The notions of graph divisor theory are in duality with the notions of the chip-firing game of Bj\"orner, Lov\'asz and Shor. We use this connection to prove Riemann--Roch-type results on directed graphs. We give a simple proof for a Riemann--Roch inequality on Eulerian directed graphs, improving a result of Amini and Manjunath. We also study possibilities and impossibilities of Riemann--Roch-type equalities in strongly connected digraphs and give examples. We intend to make the connections of this theory to graph theoretic notions more explicit via using the chip-firing framework., Comment: 22 pages, 4 figures

Keszegh (2009) proved that the extremal function e x ( n , P ) of any forbidden light 2-dimensional 0-1 matrix P is at most quasilinear in n , using a reduction to generalized Davenport–Schinzel sequences. We extend this result to multidimensional matrices by introducing a generalization of light matrices from two dimensions to higher dimensions and proving that any light d -dimensional 0-1 matrix P has extremal function e x ( n , P , d ) = O ( n d − 1 2 α ( n ) t ) for some constant t that depends on P . To prove this result, we introduce a new family of patterns called ( P , s ) -formations, which are a generalization of ( r , s ) -formations, and we prove upper bounds on their extremal functions. In many cases, including permutation matrices P with at least two ones, we are able to show that our ( P , s ) -formation upper bounds are tight.

Komlos [Tiling Turan theorems, Combinatorica, 20,2 (2000), 203{218] determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree., Comment: 13 pages, 1 figure, accepted to the European Journal of Combinatorics

A detailed description of the structure of two-ended arc-transitive digraphs is given. It is also shown that several sets of conditions, involving such concepts as Property Z, local quasi-primitivity and prime out-valency, imply that an arc-transitive digraph must be highly-arc-transitive. These are then applied to give a complete classification of two-ended highly-arc-transitive digraphs with prime in- and out-valencies., To appear in European Journal of Combinatorics. Statements of Corollaries 14, 16 and 17 corrected

Let an n × n array a i j of lights be given, each either on (when a i j = 1 ) or off (when a i j = − 1 ). For each row and each column there is a switch so that if the switch is pulled ( x i = − 1 for row i and y j = − 1 for column j ) all of the lights in that line are switched: on to off or off to on. The unbalancing lights problem (Gale–Berlekamp switching game) consists in maximizing the difference between the lights on and off. Fixed the scalar field K = R or ℂ , we obtain the exact parameters for a generalization of the unbalancing lights problem in higher dimensions m ≥ 2 , which consists in estimating, for any given n × ⋯ × n array a i 1 ⋯ i m of scalars satisfying a i 1 ⋯ i m = 1 and any given p ∈ [ 2 , ∞ ] , the expression g m , n K ( p ) = max ∑ i 1 , … , i m = 1 n a i 1 ⋯ i m x i 1 ( 1 ) ⋯ x i m ( m ) , where the maximum is evaluated for all scalars x i j ( j ) such that ‖ ( x i j ( j ) ) i = 1 n ‖ p = 1 . In the particular case m = 2 and p = ∞ , we recover the original problem.

We show that if $D$ is a tournament of arbitrary size then $D$ has finite strong components after reversing a locally finite sequence of cycles. In turn, we prove that any tournament can be covered by two acyclic sets after reversing a locally finite sequence of cycles. This provides a partial solution to a conjecture of S. Thomass\'e., Comment: 23 pages, first public version. Comments are very welcome