| 1. |
- Aaghabali, M., et al.
(författare)
-
Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
- 2015
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 45, s. 132-144
-
Tidskriftsartikel (refereegranskat)abstract
- We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on 2n vertices. The upper bound is sharp for even n. For odd n we state a conjecture on a sharp upper bound.
|
|
| 2. |
- Björner, Anders, et al.
(författare)
-
Connectivity of chamber graphs of buildings and related complexes
- 2010
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 31:8, s. 2149-2160
-
Tidskriftsartikel (refereegranskat)abstract
- Let Delta be a thick and locally finite building with the property that no edge of the associated Coxerer diagram has label "infinity". The chamber graph G(Delta), whose edges are the pairs of adjacent chambers in Delta is known to be q-regular for a certain number q = q(Delta). Our main result is that G(Delta) is q-connected in the sense of graph theory. In the language of building theory this means that every pair of chambers of Delta is connected by q pairwise disjoint galleries. Similar results are proved for the chamber graphs of Coxeter complexes and for order complexes of geometric lattices.
|
|
| 3. |
- Bränden, Petter
(författare)
-
Actions on permutations and unimodality of descent polynomials
- 2008
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 29:2, s. 514-531
-
Tidskriftsartikel (refereegranskat)abstract
- We study a group action on permutations due to Foata and Strehl and use it to prove that the descent generating polynomial of certain sets of permutations has a non-negative expansion in the basis {t(i) (1 + t)(n-1-2i)}(i=0)(m), m = [(n - 1)/2]. This property implies symmetry and unimodality. We prove that the action is invariant under stack sorting which strengthens recent unimodality results of Bona. We prove that the generalized permutation patterns (13-2) and (2-31) are invariant under the action and use this to prove unimodality properties for a q-analog of the Eulerian numbers recently studied by Corteel, Postnikov, Steingrimsson and Williams. We also extend the action to linear extensions of sign-graded posets to give a new proof of the unimodality of the (P, omega)-Eulerian polynomials of sign-graded posets and a combinatorial interpretations (in terms of Stembridge's peak polynomials) of the corresponding coefficients when expanded in the above basis. Finally, we prove that the statistic defined as the number of vertices of even height in the unordered decreasing tree of a permutation has the same distribution as the number of descents on any set of permutations invariant under the action. On restricting to the set of stack sortable permutations we recover a result of Kreweras.
|
|
| 4. |
- Cambie, Stijn, et al.
(författare)
-
On the maximum mean subtree order of trees
- 2021
-
Ingår i: European journal of combinatorics (Print). - : Elsevier. - 0195-6698 .- 1095-9971. ; 97
-
Tidskriftsartikel (refereegranskat)abstract
- A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invariant was first analyzed in the 1980s by Jamison. An intriguing open question raised by Jamison asks whether the maximum of the mean subtree order, given the order of the tree, is always attained by some caterpillar. While we do not completely resolve this conjecture, we find some evidence in its favor by proving different features of trees that attain the maximum. For example, we show that the diameter of a tree of order n with maximum mean subtree order must be very close to n. Moreover, we show that the maximum mean subtree order is equal to n - 2 log(2) n + O(1). For the local mean subtree order, which is the average order of all subtrees containing a fixed vertex, we can be even more precise: we show that its maximum is always attained by a broom and that it is equal to n - log(2) n + O(1).
|
|
| 5. |
- Casselgren, Carl Johan
(författare)
-
Coloring graphs from random lists of size 2
- 2012
-
Ingår i: European journal of combinatorics (Print). - London : Academic Press. - 0195-6698 .- 1095-9971. ; 33:2, s. 168-181
-
Tidskriftsartikel (refereegranskat)abstract
- Let G = G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Delta. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set e of size sigma (n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring phi such that phi(v) is an element of L(v) for all v is an element of V(G). In particular, we show that if g is odd and sigma (n) = omega(n(1/(2g-2))), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n --> infinity. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n >= g, there is a graph H = H(n, g) with bounded maximum degree and girth g, such that if sigma (n) = 0(n(1/(2g-2))), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n --> infinity. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size sigma (n), exhibits a sharp threshold at sigma (n) = 2n. (C) 2011 Elsevier Ltd. All rights reserved.
|
|
| 6. |
- Casselgren, Carl Johan, et al.
(författare)
-
Hadwigers Conjecture for inflations of 3-chromatic graphs
- 2016
-
Ingår i: European journal of combinatorics (Print). - : ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD. - 0195-6698 .- 1095-9971. ; 51, s. 99-108
-
Tidskriftsartikel (refereegranskat)abstract
- Hadwigers Conjecture states that every k-chromatic graph has a complete minor of order k. A graph G is an inflation of a graph G if G is obtained from G by replacing each vertex upsilon of G by a clique C-upsilon and joining two vertices of distinct cliques by an edge if and only if the corresponding vertices of G are adjacent. We present an algorithm for computing an upper bound on the chromatic number chi (G) of any inflation G of any 3-chromatic graph G. As a consequence, we deduce that Hadwigers Conjecture holds for any inflation of any 3-colorable graph. (C) 2015 Elsevier Ltd. All rights reserved.
|
|
| 7. |
- Casselgren, Carl Johan, et al.
(författare)
-
Latin cubes of even order with forbidden entries
- 2020
-
Ingår i: European journal of combinatorics (Print). - : ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD. - 0195-6698 .- 1095-9971. ; 85
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant gamma amp;gt; 0 such that if n is even and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma n times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every i, j, k is an element of {1, ..., n}, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A. (C) 2019 Elsevier Ltd. All rights reserved.
|
|
| 8. |
- Christofides, Demetres, et al.
(författare)
-
The range of thresholds for diameter 2 in random Cayley graphs
- 2014
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 35, s. 141-154
-
Tidskriftsartikel (refereegranskat)abstract
- Given a group G, the model g(G, p) denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. Given a family of groups (G(k)) and a c is an element of R+ we say that c is the threshold for diameter 2 for (G(k)) if for any epsilon > 0 with high probability Gamma is an element of g(G(k), p) has diameter greater than 2 if p <= root(c - epsilon)log n/n and diameter at most 2 if p >= root(c + epsilon)log n/n. In Christofides and Markstrom (in press) [5] we proved that if c is a threshold for diameter 2 for a family of groups (G(k)) then c is an element of [1/4, 2] and provided two families of groups with thresholds 1/4 and 2 respectively. In this paper we study the question of whether every c is an element of [1/4, 2] is the threshold for diameter 2 for some family of groups. Rather surprisingly it turns out that the answer to this question is negative. We show that every c is an element of [1/4, 4/3] is a threshold but a c is an element of (4/3, 2] is a threshold if and only if it is of the form 4n/(3n - 1) for some positive integer n.
|
|
| 9. |
- Day, A. Nicholas, et al.
(författare)
-
Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs
- 2023
-
Ingår i: European journal of combinatorics (Print). - : Elsevier. - 0195-6698 .- 1095-9971. ; 110
-
Tidskriftsartikel (refereegranskat)abstract
- The upper density of an infinite graph G with V(G)⊆N is defined as d¯(G)=lim supn→∞|V(G)∩{1,…,n}|/n. Let KN be the infinite complete graph with vertex set N. Corsten, DeBiasio, Lamaison and Lang showed that in every 2-edge-colouring of KN, there exists a monochromatic path with upper density at least (12+8)/17, which is best possible. In this paper, we extend this result to k-edge-colouring of KN for k≥3. We conjecture that every k-edge-coloured KN contains a monochromatic path with upper density at least 1/(k−1), which is best possible (when k−1 is a prime power). We prove that this is true when k=3 and asymptotically when k=4. Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest.
|
|
| 10. |
- Doolittle, Joseph, et al.
(författare)
-
Partition and Cohen-Macaulay extenders
- 2022
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 102
-
Tidskriftsartikel (refereegranskat)abstract
- If a pure simplicial complex is partitionable, then its h-vector has a combinatorial interpretation in terms of any partitioning of the complex. Given a non-partitionable complex increment , we construct a complex Gamma superset of increment of the same dimension such that both Gamma and the relative complex (Gamma , increment ) are partitionable. This allows us to rewrite the h-vector of any pure simplicial complex as the difference of two h-vectors of partitionable complexes, giving an analogous interpretation of the h-vector of a non-partitionable complex. By contrast, for a given complex increment it is not always possible to find a complex Gamma such that both Gamma and (Gamma , increment ) are Cohen- Macaulay. We characterize when this is possible, and we show that the construction of such a Gamma in this case is remarkably straightforward. We end with a note on a similar notion for shellability and a connection to Simon's conjecture on extendable shellability for uniform matroids.
|
|
