| 11. |
- Huber, K. T., et al.
(författare)
-
The relation graph
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 244:1-3, s. 153-166
-
Tidskriftsartikel (refereegranskat)abstract
- Given a set R of distinct, non-trivial partitions of a finite set, we define the relation graph G(R) of R. In case R consists only of bipartitions, G(R) is the well-known Buneman graph, a median graph that has applications in the area of phylogenetic analysis., Here we consider properties of the relation graph for general sets of partitions and, in particular, we see that it mimics the behaviour of the Buneman graph by proving the following two theorems:(i) The graph G(R) is a Hamming graph if and only if R is strongly incompatible.(ii) The graph G(R) is a block graph with #R blocks if and only if R is strongly compatible.
|
|
| 12. |
- Linusson, Svante
(författare)
-
Extended pattern avoidance
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 246:1-3, s. 219-230
-
Tidskriftsartikel (refereegranskat)abstract
- A 0-1 matrix is said to be extendably tau-avoiding if it can be the upper left corner of a tau-avoiding permutation matrix. This concept arose in Eriksson and Linusson (Electron. J. Combin. 2 (1995) R6) where the surprising result that the number of extendably 321-avoiding rectangles are enumerated by the ballot numbers was proved, Here we study the other five patterns of length three. The main result is that the six patterns of length three divide into only two cases, no easy symmetry can explain this. Another result is that the Simion-Schmidt-West bijection for permutations avoiding patterns 12tau and 21tau works also for extended pattern avoidance. As an application, we use the results on extended pattern avoidance to prove a sequence of refinements on the enumeration of permutations avoiding patterns of length 3. The results and proofs use many properties and refinements of the Catalan numbers. (C) 2002 Elsevier Science B.V. All rights reserved.
|
|
| 13. |
- Lundow, Per Håkan
(författare)
-
Compression of transfer matrices
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 231:03-jan, s. 321-329
-
Tidskriftsartikel (refereegranskat)abstract
- We present a method for reducing the size of transfer matrices by exploiting symmetry. For example, the transfer matrix for enumeration of matchings in the graph C-4 x C-4 x P-n can be reduced from order 65536 to 402 simply due to the 384 automorphisms of C-4 x C-4. The matrix for enumeration of perfect matchings can be still further reduced to order 93, all in a straightforward and mechanical way. As an application we report an improved upper bound for the three-dimensional dimer problem.
|
|
| 14. |
- Adamaszek, Michal, et al.
(författare)
-
On a lower bound for the connectivity of the independence complex of a graph
- 2011
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 311:21, s. 2566-2569
-
Tidskriftsartikel (refereegranskat)abstract
- Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.
|
|
| 15. |
- Alexandersson, Per, et al.
(författare)
-
LLT polynomials, chromatic quasisymmetric functions and graphs with cycles
- 2018
-
Ingår i: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 341:12, s. 3453-3482
-
Tidskriftsartikel (refereegranskat)abstract
- We use a Dyck path model for unit-interval graphs to study the chromatic quasisymmetric functions introduced by Shareshian and Wachs, as well as unicellular LLT polynomials, revealing some parallel structure and phenomena regarding their e-positivity. The Dyck path model is also extended to circular arc digraphs to obtain larger families of polynomials, giving a new extension of LLT polynomials. Carrying over a lot of the noncircular combinatorics, we prove several statements regarding the e-coefficients of chromatic quasisymmetric functions and LLT polynomials, including a natural combinatorial interpretation for the e-coefficients for the line graph and the cycle graph for both families. We believe that certain e-positivity conjectures hold in all these families above. Furthermore, beyond the chromatic analogy, we study vertical-strip LLT polynomials, which are modified Hall-Littlewood polynomials.
|
|
| 16. |
- Amini, Nima, et al.
(författare)
-
The cone of cyclic sieving phenomena
- 2019
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 342:6, s. 1581-1601
-
Tidskriftsartikel (refereegranskat)abstract
- We study cyclic sieving phenomena (CSP) on combinatorial objects from an abstract point of view by considering a rational polyhedral cone determined by the linear equations that define such phenomena. Each lattice point in the cone corresponds to a non-negative integer matrix which jointly records the statistic and cyclic order distribution associated with the set of objects realizing the CSP. In particular we consider a universal subcone onto which every CSP matrix linearly projects such that the projection realizes a CSP with the same cyclic orbit structure, but via a universal statistic that has even distribution on the orbits.Reiner et.al. showed that every cyclic action gives rise to a unique polynomial (mod q^n-1) complementing the action to a CSP. We give a necessary and sufficient criterion for the converse to hold. This characterization allows one to determine if a combinatorial set with a statistic gives rise (in principle) to a CSP without having a combinatorial realization of the cyclic action. We apply the criterion to conjecture a new CSP involving stretched Schur polynomials and prove our conjecture for certain rectangular tableaux. Finally we study some geometric properties of the CSP cone. We explicitly determine its half-space description and in the prime order case we determine its extreme rays.
|
|
| 17. |
- Andriantiana, Eric Ould Dadah, et al.
(författare)
-
Trees with minimum number of infima closed sets
- 2022
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 345:5
-
Tidskriftsartikel (refereegranskat)abstract
- Let T be a rooted tree, and V(T) its set of vertices. A subset X of V(T) is called an infima closed set of T if for any two vertices u, v is an element of X, the first common ancestor of u and v is also in X. This paper determines the trees with minimum number of infima closed sets among all rooted trees of given order, thereby answering a question of Klazar. It is shown that these trees are essentially complete binary trees, with the exception of vertices at the last levels. Moreover, an asymptotic estimate for the minimum number of infima closed sets in a tree with n vertices is also provided.
|
|
| 18. |
- Asratian, Armen, et al.
(författare)
-
On interval edge colorings of (a, ß)-biregular bipartite graphs
- 2007
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 307:15, s. 1951-1956
-
Tidskriftsartikel (refereegranskat)abstract
- A bipartite graph G is called (a, ß)-biregular if all vertices in one part of G have degree a and all vertices in the other part have degree ß. An edge coloring of a graph G with colors 1, 2, 3, ..., t is called an interval t-coloring if the colors received by the edges incident with each vertex of G are distinct and form an interval of integers and at least one edge of G is colored i, for i = 1, ..., t. We show that the problem to determine whether an (a, ß)-biregular bipartite graph G has an interval t-coloring is NP-complete in the case when a = 6, ß = 3 and t = 6. It is known that if an (a, ß)-biregular bipartite graph G on m vertices has an interval t-coloring then a + ß - gcd (a, ß) = t = m - 1, where gcd (a, ß) is the greatest common divisor of a and ß. We prove that if an (a, ß)-biregular bipartite graph has m = 2 (a + ß) vertices then the upper bound can be improved to m - 3. © 2006 Elsevier B.V. All rights reserved.
|
|
| 19. |
- Bagan, Guillaume, et al.
(författare)
-
Incidence, a scoring positional game on graphs
- 2023
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X.
-
Tidskriftsartikel (refereegranskat)abstract
- Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on INCIDENCE, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of INCIDENCE is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.
|
|
| 20. |
- Björklund, Johan, et al.
(författare)
-
Counterexamples to a monotonicity conjecture for the threshold pebbling number
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:15, s. 2401-2405
-
Tidskriftsartikel (refereegranskat)abstract
- Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move, in which two pebbles are removed from a vertex and one is placed on a neighbouring vertex. Given a graph G, the pebbling number pi (G) is the least t such that every initial distribution of t pebbles at the vertices of G is solvable, that is for every target vertex nu, there is some list of pebbling moves that ends with nu having a pebble. Given a graph sequence (G(n)), the pebbling threshold tau (G(n)) is a sequence (a(n)) such that t = a(n) is the smallest number of pebbles such that a random configuration of t pebbles on the vertices of G(n) is solvable with probability at least 1/2, in the probabilistic model where each configuration oft pebbles on the vertices of G(n) is selected uniformly at random. This paper provides counterexamples to the following monotonicity conjecture stated by Hurlbert et al.: If (G(n)) and (H-n) are graph sequences such that pi(G(n)) <= pi(H-n), then it holds that tau(G(n)) is an element of O(tau(H-n)).
|
|
