Authors:Julien Baste; Marc Noy; Ignasi Sau Pages: 12 - 21 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Julien Baste, Marc Noy, Ignasi Sau Let T n , k be the number of labeled graphs on n vertices and treewidth at most k (equivalently, the number of labeled partial k -trees). We show that c k 2 k n log k n 2 − k ( k + 3 ) 2 k − 2 k − 2 ≤ T n , k ≤ k 2 k n n 2 − k ( k + 1 ) 2 k − k , for k > 1 and some explicit absolute constant c > 0 . Disregarding terms depending only on k , the gap between the lower and upper bound is of order ( log k ) n . The upper bound is a direct consequence of the well-known formula for the number of labeled k -trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k .

Authors:Lele Liu; Liying Kang; Erfang Shan Pages: 22 - 32 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Lele Liu, Liying Kang, Erfang Shan Let H be an r -uniform hypergraph on n vertices and m edges, and let d i be the degree of i ∈ V ( H ) . Denote by ε ( H ) the difference between the spectral radius of H and the average degree of H . Also, denote s ( H ) = ∑ i ∈ V ( H ) d i − r m n , v ( H ) = 1 n ∑ i ∈ V ( H ) d i r r − 1 − r m n r r − 1 . In this paper, we investigate the irregularity of r -uniform hypergraph H with respect to ε ( H ) , s ( H ) and v ( H ) , which extend relevant results to uniform hypergraphs.

Authors:Huan Xiong Pages: 33 - 42 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Huan Xiong We derive the largest sizes of ( t , m t + 1 ) and ( t , m t − 1 ) -core partitions with distinct parts, and prove that the numbers of such partitions with the largest sizes are at most 2. This work is motivated by Amdeberhan’s conjecture on ( t , t + 1 ) -core partitions with distinct parts and subsequent research on the enumeration, largest sizes and the average sizes of simultaneous core partitions with distinct parts.

Authors:Tomasz Łuczak; Joanna Polcyn; Andrzej Ruciński Pages: 43 - 50 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Tomasz Łuczak, Joanna Polcyn, Andrzej Ruciński We show that there exists an absolute constant A such that for each k ≥ 2 and every coloring of the edges of the complete k -uniform hypergraph on A r vertices with r colors, r ≥ r k , one of the color classes contains a loose path of length three.

Authors:Jan Corsten; Nóra Frankl Pages: 51 - 54 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Jan Corsten, Nóra Frankl A finite set A ⊂ R d is called diameter-Ramsey if for every r ∈ N , there exists some n ∈ N and a finite set B ⊂ R n with diam ( A ) = diam ( B ) such that whenever B is coloured with r colours, there is a monochromatic set A ′ ⊂ B which is congruent to A . We prove that sets of diameter 1 with circumradius larger than 1 ∕ 2 are not diameter-Ramsey. In particular, we obtain that triangles with an angle larger than 135° are not diameter-Ramsey, improving a result of Frankl, Pach, Reiher and Rödl. Furthermore, we deduce that there are simplices which are almost regular but not diameter-Ramsey.

Authors:Eric Hoffbeck; Ieke Moerdijk Pages: 55 - 72 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Eric Hoffbeck, Ieke Moerdijk We discuss a notion of shuffle for trees which extends the usual notion of a shuffle for two natural numbers. We give several equivalent descriptions, and prove some algebraic and combinatorial properties. In addition, we characterize shuffles in terms of open sets in a topological space associated to a pair of trees. Our notion of shuffle is motivated by the theory of operads and occurs in the theory of dendroidal sets, but our presentation is independent and entirely self-contained.

Authors:Guo-Niu Han; Jing-Yi Liu Pages: 99 - 110 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Guo-Niu Han, Jing-Yi Liu The tangent number T 2 n + 1 is equal to the number of increasing labelled complete binary trees with 2 n + 1 vertices. This combinatorial interpretation immediately proves that T 2 n + 1 is divisible by 2 n . However, a stronger divisibility property is known in the studies of Bernoulli and Genocchi numbers, namely, the divisibility of ( n + 1 ) T 2 n + 1 by 2 2 n . The traditional proofs of this fact need significant calculations. In the present paper, we provide a combinatorial proof of the latter divisibility by using the hook length formula for trees. Furthermore, our method is extended to k -ary trees, leading to a new generalization of the Genocchi numbers.

Authors:Lale Özkahya; Yury Person Pages: 111 - 124 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Lale Özkahya, Yury Person Given graphs G and H , we consider the problem of decomposing a properly edge-colored graph G into few parts consisting of rainbow copies of H and single edges. We establish a close relation to the previously studied problem of minimum H -decompositions, where an edge coloring does not matter and one is merely interested in decomposing graphs into copies of H and single edges.

Authors:Edward Richmond; William Slofstra Pages: 125 - 138 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Edward Richmond, William Slofstra We show that every smooth Schubert variety of affine type A ̃ is an iterated fibre bundle of Grassmannians, extending an analogous result by Ryan and Wolper for Schubert varieties of finite type A . As a consequence, we finish a conjecture of Billey–Crites that a Schubert variety in affine type A ̃ is smooth if and only if the corresponding affine permutation avoids the patterns 4231 and 3412. Using this iterated fibre bundle structure, we compute the generating function for the number of smooth Schubert varieties of affine type A ̃ .

Authors:Donglei Yang; Yandong Bai; Guanghui Wang; Jianliang Wu Pages: 174 - 179 Abstract: Publication date: June 2018 Source:European Journal of Combinatorics, Volume 71 Author(s): Donglei Yang, Yandong Bai, Guanghui Wang, Jianliang Wu In 1995, Stiebitz asked the following question: For any positive integers s , t , is there a finite integer f ( s , t ) such that every digraph D with minimum out-degree at least f ( s , t ) admits a bipartition ( A , B ) such that A induces a subdigraph with minimum out-degree at least s and B induces a subdigraph with minimum out-degree at least t ' We give an affirmative answer for tournaments, multipartite tournaments, and digraphs with bounded maximum in-degrees. In particular, we show that for every ϵ with 0 < ϵ < 1 ∕ 2 , there exists an integer δ 0 such that every tournament with minimum out-degree at least δ 0 admits a bisection ( A , B ) , so that each vertex has at least ( 1 ∕ 2 − ϵ ) of its out-neighbors in A , and in B as well.

Authors:Wenjie Fang Pages: 75 - 91 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Wenjie Fang We present a direct bijection between planar 3-connected triangulations and bridgeless planar maps, which were first enumerated by Tutte (1962) and Walsh and Lehman (1975) respectively. Previously known bijections by Wormald (1980) and Fusy (2010) are all defined recursively. Our direct bijection passes by a new class of combinatorial objects called “sticky trees”. We also present bijections between sticky trees, intervals in the Tamari lattices and closed flows on forests. With our bijections, we recover several known enumerative results about these objects. We thus show that sticky trees can serve as a nexus of bijective links among all these equi-enumerated objects.

Authors:Victor J.W. Guo Pages: 92 - 98 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Victor J.W. Guo In an approach to the Cayley formula for counting trees, Shor discovered a refined recurrence relation concerning the number of improper edges. Chen and the author gave a bijection for the Shor recurrence based on the combinatorial interpretations of Zeng, answering a question of Shor. In this paper, we present a new bijective proof of the Shor recurrence by applying Shor’s formula for counting forests of rooted trees with roots 1 , … , r and with a given number of improper edges.

Authors:Dennis Clemens; Shagnik Das; Tuan Tran Pages: 99 - 124 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Dennis Clemens, Shagnik Das, Tuan Tran The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.

Authors:Béla Bollobás; Jonathan Lee; Shoham Letzter Pages: 125 - 148 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Béla Bollobás, Jonathan Lee, Shoham Letzter We consider the problem of maximising the largest eigenvalue of subgraphs of the hypercube Q d of a given order. We believe that in most cases, Hamming balls are maximisers, and our results support this belief. We show that the Hamming balls of radius o ( d ) have largest eigenvalue that is within 1 + o ( 1 ) of the maximum value. We also prove that Hamming balls with fixed radius maximise the largest eigenvalue exactly, rather than asymptotically, when d is sufficiently large. Our proofs rely on the method of compressions.

Authors:David Ellis; Imre Leader Pages: 149 - 154 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): David Ellis, Imre Leader We say a family of subsets of { 1 , 2 , … , n } is antipodal if it is closed under taking complements. We prove a best-possible isoperimetric inequality for antipodal families of subsets of { 1 , 2 , … , n } (of any size). Our inequality implies that for any k ∈ N , among all such families of size 2 k , a family consisting of the union of two antipodal ( k − 1 ) -dimensional subcubes has the smallest possible edge boundary.

Authors:Michael Bennett Pages: 155 - 163 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Michael Bennett Here we examine some Erdős–Falconer-type problems in vector spaces over finite fields involving right angles. Our main goals are to show that (a) a subset A ⊂ F q d of size ≥ c q d + 2 3 contains three points which generate a right angle, and (b) a subset A ⊂ F q d of size ≥ C q d + 2 2 contains two points which generate a right angle with the vertex at the origin. We will also prove that (b) is sharp up to constants and provide some partial results for similar problems related to spread and collinear triples.

Authors:Jiaao Li; Carsten Thomassen; Yezhou Wu; Cun-Quan Zhang Pages: 164 - 177 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Jiaao Li, Carsten Thomassen, Yezhou Wu, Cun-Quan Zhang We prove that, for any natural number p , the flow index ϕ ( G ) < 2 + 1 p if and only if G has a strongly connected modulo ( 2 p + 1 ) -orientation. For the case p = 1 we prove that the flow index of every 8-edge-connected graph is strictly less than 3.

Authors:Thomas Hudson; Tomoo Matsumura Pages: 190 - 201 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Thomas Hudson, Tomoo Matsumura In this paper, we prove determinantal formulas for the K -theory classes of the structure sheaves of degeneracy loci associated to vexillary permutations in type A . As a consequence we obtain determinantal formulas for Lascoux–Schützenberger’s double Grothendieck polynomials associated to vexillary permutations. We also prove a generalization of the formula in algebraic cobordism.

Authors:Zhicong Lin Pages: 202 - 211 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Zhicong Lin We prove a conjecture due independently to Yan and Martinez–Savage that asserts inversion sequences with no weakly decreasing subsequence of length 3 and enhanced 3-noncrossing partitions have the same cardinality. Our approach applies both the generating tree technique and the so-called obstinate kernel method developed by Bousquet-Mélou. One application of this equinumerosity is a discovery of an intriguing identity involving numbers of classical and enhanced 3-noncrossing partitions.

Authors:Shinya Fujita; Henry Liu; Amites Sarkar Pages: 212 - 231 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Shinya Fujita, Henry Liu, Amites Sarkar Let G be a graph on n vertices with independence number α . We prove that if n is sufficiently large ( n ≥ α 2 k + 1 will do), then G always contains a k -connected subgraph on at least n ∕ α vertices. The value of n ∕ α is sharp, since G might be the disjoint union of α equally-sized cliques. For k ≥ 3 and α = 2 , 3 , we shall prove that the same result holds for n ≥ 4 ( k − 1 ) and n ≥ 27 ( k − 1 ) 4 respectively, and that these lower bounds on n are sharp.

Authors:Koji Momihara Pages: 232 - 250 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Koji Momihara In this paper, we give a construction of strongly regular Cayley graphs on the additive groups of finite fields based on three-valued Gauss periods. As consequences, we obtain two infinite families and one sporadic example of new strongly regular Cayley graphs. This construction can be viewed as a generalization of that of strongly regular Cayley graphs obtained in Bamberg et al. (0000).

Authors:R. Balasubramanian; Prem Prakash Pandey Pages: 284 - 296 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): R. Balasubramanian, Prem Prakash Pandey The “structure theory of set addition” has been well studied in the last fifty years, after the works of Freiman. In [1] Deshouillers and Freiman established a structure theorem for subsets of Z ∕ n Z with small doubling constant. In this article we provide a simpler proof of the structure theorem of [1], and on our way we also obtain some improvements.

Authors:Zemin Jin; Kecai Ye; Yuefang Sun; He Chen Pages: 297 - 316 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Zemin Jin, Kecai Ye, Yuefang Sun, He Chen In 1973, Erdős et al. introduced the anti-Ramsey number for a graph G in K n , which is defined to be the maximum number of colors in an edge-coloring of K n which does not contain any rainbow G . This is always regarded as one of rainbow generalizations of the classic Ramsey theory. Since then the anti-Ramsey numbers for several special graph classes in complete graphs have been determined. Also, the researchers generalized the host graph for the anti-Ramsey number from the complete graph to general graphs, including bipartite graphs, complete split graphs, planar graphs, and so on. In this paper, we study the anti-Ramsey number of matchings in the complete split graph. Since the complete split graph contains the complete graph as a subclass, the results in this paper cover the previous results about the anti-Ramsey number of matchings in the complete graph.

Authors:Shane Chern; Ae Ja Yee Pages: 317 - 324 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Shane Chern, Ae Ja Yee We generalize recent results of Breuer and Kronholm, and Chern on partitions and overpartitions with bounded differences between largest and smallest parts. We prove our generalization both analytically and combinatorially.

Authors:Angèle M. Foley; Ronald C. King Pages: 325 - 353 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Angèle M. Foley, Ronald C. King Just as the definition of factorial Schur functions as a ratio of determinants allows one to show that they satisfy a Jacobi–Trudi-type identity and have an explicit combinatorial realisation in terms of semistandard tableaux, so we offer here definitions of factorial irreducible characters of the classical Lie groups as ratios of determinants that share these two features. These factorial characters are each specified by a partition, λ = ( λ 1 , λ 2 , … , λ n ) , and in each case a flagged Jacobi–Trudi identity is derived that expresses the factorial character as a determinant of corresponding factorial characters specified by one-part partitions, ( m ) , for which we supply generating functions. These identities are established by manipulating determinants through the use of certain recurrence relations derived from these generating functions. The transitions to combinatorial realisations of the factorial characters in terms of tableaux are then established by means of non-intersecting lattice path models. The results apply to g l ( n ) , s o ( 2 n + 1 ) , s p ( 2 n ) and o ( 2 n ) , and are extended to the case of s o ( 2 n ) by making use of newly defined factorial difference characters.

Authors:Richard A. Moy; Mehtaab Sawhney; David Stoner Pages: 354 - 363 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Richard A. Moy, Mehtaab Sawhney, David Stoner Odlyzko and Stanley introduced a greedy algorithm for constructing infinite sequences with no 3-term arithmetic progressions when beginning with a finite set with no 3-term arithmetic progressions. The sequences constructed from this procedure are known as Stanley sequences and appear to have two distinct growth rates which dictate whether the sequences are structured or chaotic. A large subclass of sequences of the former type is independent sequences, which have a self-similar structure. An attribute of interest for independent sequences is the character. In this paper, building on recent progress, we prove that every nonnegative integer λ ∉ { 1 , 3 , 5 , 9 , 11 , 15 } is attainable as the character of an independent Stanley sequence, thus resolving a conjecture of Rolnick.

Authors:Andrzej Dudek; Xavier Pérez-Giménez; Paweł Prałat; Hao Qi; Douglas West; Xuding Zhu Pages: 364 - 373 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Andrzej Dudek, Xavier Pérez-Giménez, Paweł Prałat, Hao Qi, Douglas West, Xuding Zhu A twisted hypercube of dimension k is created from two twisted hypercubes of dimension k − 1 by adding a matching joining their vertex sets, with the twisted hypercube of dimension 0 consisting of one vertex and no edges. We generate random twisted hypercube by generating the matchings randomly at each step. We show that, asymptotically almost surely, joining any two vertices in a random twisted hypercube of dimension k there are k internally disjoint paths of length at most k lg k + O k lg 2 k . Since the graph is k -regular with 2 k vertices, the number of paths is optimal and the length is asymptotically optimal.

Authors:Takayuki Hibi; Akihiro Higashitani; Koutarou Yoshida Pages: 374 - 383 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Takayuki Hibi, Akihiro Higashitani, Koutarou Yoshida Given integers k and m with k ≥ 2 and m ≥ 2 , let P be an empty simplex of dimension ( 2 k − 1 ) whose δ -polynomial is of the form 1 + ( m − 1 ) t k . In the present paper, the necessary and sufficient condition for the k th dilation k P of P to have a regular unimodular triangulation will be presented.

Authors:Carsten R. Seemann; Marc Hellmuth Pages: 384 - 407 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Carsten R. Seemann, Marc Hellmuth The closure cl ( R ) of a consistent set R of triples (rooted binary trees on three leaves) provides essential information about tree-like relations that are shown by any supertree that displays all triples in R . In this contribution, we are concerned with representative triple sets, that is, subsets R ′ of R with cl ( R ′ ) = cl ( R ) . In this case, R ′ still contains all information on the tree structure implied by R , although R ′ might be significantly smaller. We show that representative triple sets that are minimal w.r.t. inclusion form the basis of a matroid. This in turn implies that minimal representative triple sets also have minimum cardinality. In particular, the matroid structure can be used to show that minimum representative triple sets can be computed in polynomial time with a simple greedy approach. For a given triple set R that “identifies” a tree, we provide an exact value for the cardinality of its minimum representative triple sets. In addition, we utilize the latter results to provide a novel and efficient method to compute the closure cl ( R ) of a consistent triple set R that improves the time complexity O ( R L R 4 ) of the currently fastest known method proposed by Bryant and Steel (1995). In particular, if a minimum representative triple set for R is given, it can be shown that the time complexity to compute cl ( R ) can be improved by a factor up to R L R . As it turns out, collections of quartets (unrooted binary trees on four leaves) do not provide a matroid structure, in general.

Authors:Daniel Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Daniel Soltész We say that a pair ( A , B ) is a recovering pair if A and B are set systems on an n -element ground set, such that for every A , A ′ ∈ A and B , B ′ ∈ B we have ( A ∖ B = A ′ ∖ B ′ implies A = A ′ ) and symmetrically ( B ∖ A = B ′ ∖ A ′ implies B = B ′ ). G. Simonyi conjectured that if ( A , B ) is a recovering pair, then A B ≤ 2 n . For the quantity A B the best known upper bound is 2 . 326 4 n due to Holzman and Körner. In this paper we improve this upper bound to 2 . 281 4 n .

Authors:Dragan Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Dragan Mašulović Showing that the Ramsey property holds for a class of finite structures can be an extremely challenging task and a slew of sophisticated methods have been proposed in literature. In this paper we propose a new strategy to show that a class of structures has the Ramsey property. The strategy is based on a relatively simple result in category theory and consists of establishing a pre-adjunction between the category of structures which is known to have the Ramsey property, and the category of structures we are interested in. We demonstrate the applicability of this strategy by providing short proofs of three important well known results: we show the Ramsey property for the category of all finite linearly ordered posets with embeddings, for the category of finite convexly ordered ultrametric spaces with embeddings, and for the category of all finite linearly ordered metric spaces (rational metric spaces) with embeddings.

Authors:Mark Lancaster; Toufik Mansour; Shashikant Mulay; Mark Shattuck Abstract: Publication date: Available online 8 April 2018 Source:European Journal of Combinatorics Author(s): Mark Lancaster, Toufik Mansour, Shashikant Mulay, Mark Shattuck

Authors:Mustapha Kabil; Maurice Pouzet; Ivo G. Rosenberg Abstract: Publication date: Available online 2 April 2018 Source:European Journal of Combinatorics Author(s): Mustapha Kabil, Maurice Pouzet, Ivo G. Rosenberg Let A be an ordered alphabet, A ∗ be the free monoid over A ordered by the Higman ordering, and let F ( A ∗ ) be the set of final segments of A ∗ . With the operation of concatenation, this set is a monoid. We show that the submonoid F ∘ ( A ∗ ) ≔ F ( A ∗ ) ∖ { ∅ } is free. The MacNeille completion N ( A ∗ ) of A ∗ is a submonoid of F ( A ∗ ) . As a corollary, we obtain that the monoid N ∘ ( A ∗ ) ≔ N ( A ∗ ) ∖ { ∅ } is free. We give an interpretation of the freeness of F ∘ ( A ∗ ) in the category of metric spaces over the Heyting algebra V ≔ F ( A ∗ ) , with the non-expansive mappings as morphisms. Each final segment F of A ∗ yields the injective envelope S F of a two-element metric space over V . The uniqueness of the decomposition of F is due to the uniqueness of the block decomposition of the graph G F associated to this injective envelope.

Authors:Vadim E. Levit; Eugen Mandrescu Abstract: Publication date: Available online 17 March 2018 Source:European Journal of Combinatorics Author(s): Vadim E. Levit, Eugen Mandrescu A graph is well-covered if all its maximal independent sets are of the same size (Plummer, 1970). A well-covered graph is 1-well-covered if the deletion of any one vertex leaves a graph, which is well-covered as well (Staples, 1975). A graph G belongs to class W n if every n pairwise disjoint independent sets in G are included in n pairwise disjoint maximum independent sets (Staples, 1975). Clearly, W 1 is the family of all well-covered graphs. It turns out that G ∈ W 2 if and only if it is a 1-well-covered graph without isolated vertices. We show that deleting a shedding vertex does not change the maximum size of a maximal independent set including a given independent set. Specifically, for well-covered graphs, it means that the vertex v is shedding if and only if G − v is well-covered. In addition, we provide new characterizations of 1-well-covered graphs.

Authors:Adel Alahmadi; Michel Deza; Mathieu Dutour Sikirić; Patrick Solé Abstract: Publication date: Available online 17 March 2018 Source:European Journal of Combinatorics Author(s): Adel Alahmadi, Michel Deza, Mathieu Dutour Sikirić, Patrick Solé 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.

Authors:Jin Akiyama; Kiyoko Matsunaga Abstract: Publication date: Available online 10 March 2018 Source:European Journal of Combinatorics Author(s): Jin Akiyama, Kiyoko Matsunaga 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 Theorems 3 and 4, we give the sufficient conditions for Conway tiles to be foldable into envelopes.

Authors:Gaspar Mayor; Oscar Valero Abstract: Publication date: Available online 9 March 2018 Source:European Journal of Combinatorics Author(s): Gaspar Mayor, Oscar Valero In 1981, J. Borsík and J. Doboš analyzed what properties a function must satisfy in order to merge a collection of metric spaces into a single one. Later on, E. Castiñeira, 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.

Authors:Vidali Abstract: Publication date: Available online 5 March 2018 Source:European Journal of Combinatorics Author(s): A. Jurišić, J. Vidali The combinatorial structure of a famous graph with large girth, namely the Sylvester graph, is studied. Simple techniques, such as two-way counting, partitions, circuit chasing and covers are used to identify smaller structures and to show that there are no other graphs that share a small number of regularity properties with it. As a consequence, we show the same for the Hoffman–Singleton graph. We notice that some much larger graphs with large girth have similar properties, and could be studied using the same techniques. In particular, we show that just as the Hoffman–Singleton graph contains the Sylvester graph, a Moore graph of valency 57, whose existence is a famous open problem, must contain a subgraph with a structure that is similar to the one we derived for the Sylvester graph.

Authors:Rafael G.L. D’Oliveira; Marcelo Firer Abstract: Publication date: Available online 5 March 2018 Source:European Journal of Combinatorics Author(s): Rafael G.L. D’Oliveira, Marcelo Firer We present an algorithm that, given a channel, determines if there is a distance for it such that the maximum likelihood decoder coincides with the minimum distance decoder. We also show that any metric, up to a decoding equivalence, can be isometrically embedded into the hypercube with the Hamming metric, and thus, in terms of decoding, the Hamming metric is universal.

Authors:N. Dolbilin; M. Bouniaev Abstract: Publication date: Available online 5 March 2018 Source:European Journal of Combinatorics Author(s): N. Dolbilin, M. Bouniaev 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.

Authors:Zhi Qiao; Jongyook Park; Jack H. Koolen Abstract: Publication date: Available online 5 March 2018 Source:European Journal of Combinatorics Author(s): Zhi Qiao, Jongyook Park, Jack H. Koolen 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 ) .

Authors:Dmitry Malinin Abstract: Publication date: Available online 2 March 2018 Source:European Journal of Combinatorics Author(s): Dmitry Malinin 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.

Authors:Davide Bolognini; Antonio Macchia; Francesco Strazzanti Pages: 1 - 25 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Davide Bolognini, Antonio Macchia, Francesco Strazzanti Binomial edge ideals are a noteworthy class of binomial ideals that can be associated with graphs, generalizing the ideals of 2-minors. For bipartite graphs we prove the converse of Hartshorne’s Connectedness Theorem, according to which if an ideal is Cohen–Macaulay, then its dual graph is connected. This allows us to classify Cohen–Macaulay binomial edge ideals of bipartite graphs, giving an explicit and recursive construction in graph-theoretical terms. This result represents a binomial analogue of the celebrated characterization of (monomial) edge ideals of bipartite graphs due to Herzog and Hibi (2005).

Authors:Alejandro H. Morales; Igor Pak; Greta Panova Pages: 26 - 49 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): Alejandro H. Morales, Igor Pak, Greta Panova We give new bounds and asymptotic estimates on the number of standard Young tableaux of skew shape in a variety of special cases. Our approach is based on Naruse’s hook-length formula. We also compare our bounds with the existing bounds on the numbers of linear extensions of the corresponding posets.

Authors:S.D. Adhikari; L. Boza; S. Eliahou; M.P. Revuelta; M.I. Sanz Pages: 50 - 60 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): S.D. Adhikari, L. Boza, S. Eliahou, M.P. Revuelta, M.I. Sanz We show that, for every positive integer r , there exists an integer b = b ( r ) such that the 4-variable quadratic Diophantine equation ( x 1 − y 1 ) ( x 2 − y 2 ) = b is r -regular. Our proof uses Szemerédi’s theorem on arithmetic progressions.

Authors:S.V. Konyagin; I.D. Shkredov Pages: 61 - 74 Abstract: Publication date: May 2018 Source:European Journal of Combinatorics, Volume 70 Author(s): S.V. Konyagin, I.D. Shkredov We prove that asymptotically almost surely, the random Cayley sum graph over a finite abelian group G has edge density close to the expected one on every induced subgraph of size at least log c G , for any fixed c > 1 and G large enough.