| 21. |
- Borzi, Alessio, et al.
(författare)
-
The leading coefficient of Lascoux polynomials
- 2023
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 346:2
-
Tidskriftsartikel (refereegranskat)abstract
- Lascoux polynomials have been recently introduced to prove polynomiality of the maximum-likelihood degree of linear concentration models. We find the leading coefficient of the Lascoux polynomials (type C) and their generalizations to the case of general matrices (type A) and skew symmetric matrices (type D). In particular, we determine the degrees of such polynomials. As an application, we find the degree of the polynomial 8(m, n, n - s) of the algebraic degree of semidefinite programming, and when s =1 we find its leading coefficient for types C, A and D.
|
|
| 22. |
- Bränden, Petter
(författare)
-
q-Narayana numbers and the flag h-vector
- 2004
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 281:03-jan, s. 67-81
-
Tidskriftsartikel (refereegranskat)abstract
- The Narayana numbers are N(n,k) = (1/n)((n)(k))((n)(k+1)). There are several natural statistics on Dyck paths with a distribution given by N(n, k). We show the equidistribution of Narayana statistics by computing the flag h-vector of J(2 x n) in different ways. In the process we discover new Narayana statistics and provide co-statistics for the Narayana statistics so that the bi-statistics have a distribution given by Furlinger and Hofbauer's q-Narayana numbers. We interpret the flag h-vector in terms of semi-standard Young tableaux, which enables us to express the q-Narayana numbers in terms of Schur functions. We also introduce what we call pre-shellings of simplicial complexes.
|
|
| 23. |
- Casselgren, Carl Johan
(författare)
-
Anote on one-sided interval edge colorings of bipartite graphs
- 2022
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 345:2
-
Tidskriftsartikel (refereegranskat)abstract
- For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int) (G, X) the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial P(Delta) such that if G has maximum degree at most A, then chi(int)(G, X) <= P(A). In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on chi(int)(G, X) for bipartite graphs with small maximum degree. (C) 2021 The Author(s). Published by Elsevier B.V.
|
|
| 24. |
- Casselgren, Carl Johan, et al.
(författare)
-
Completing partial Latin squares with one filled row, column and symbol
- 2013
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 313:9, s. 1011-1017
-
Tidskriftsartikel (refereegranskat)abstract
- Let P be an n×n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbol s. Assume further that s is the symbol of cell (r,c) in P. We prove that P is completable to a Latin square if n≥8 and n is divisible by 4, or n≤7 and n∉{3,4,5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square.
|
|
| 25. |
- Casselgren, Carl Johan, 1982-
(författare)
-
On avoiding some families of arrays
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:5, s. 963-972
-
Tidskriftsartikel (refereegranskat)abstract
- An n×n array A with entries from {1,…,n} is avoidable if there is an n×n Latin square L such that no cell in L contains a symbol that occurs in the corresponding cell in A. We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is NP-complete, even in the case when the array has entries from only two distinct symbols. Assuming that P≠NP, this disproves a conjecture by Öhman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order n≥2k with entries from at most k distinct symbols and where each symbol occurs in at most n−2 cells is avoidable, and every single entry array of order n, where each of the symbols 1,…,n occurs in at most cells, is avoidable. Additionally, if k≥2, then every single entry array of order at least n≥4, where at most k rows contain non-empty cells and where each symbol occurs in at most n−k+1 cells, is avoidable.
|
|
| 26. |
- Casselgren, Carl Johan, et al.
(författare)
-
On interval and cyclic interval edge colorings of (3,5)-biregular graphs
- 2017
-
Ingår i: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 340:11, s. 2678-2687
-
Tidskriftsartikel (refereegranskat)abstract
- A proper edge coloring f of a graph G with colors 1, 2, 3, . . . , t is called an interval coloring if the colors on the edges incident to every vertex of G form an interval of integers. The coloring f is cyclic interval if for every vertex v of G, the colors on the edges incident to v either form an interval or the set {1, . . . t} \ {f (e) : e is incident to v} is an interval. A bipartite graph G is (a, b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b; it has been conjectured that all such graphs have interval colorings. We prove that every (3, 5)-biregular graph has a cyclic interval coloring and we give several sufficient conditions for a (3, 5)-biregular graph to admit an interval coloring. (C) 2016 Elsevier B.V. All rights reserved.
|
|
| 27. |
- Casselgren, Carl Johan, et al.
(författare)
-
One-sided interval edge-colorings of bipartite graphs
- 2016
-
Ingår i: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 339:11, s. 2628-2639
-
Tidskriftsartikel (refereegranskat)abstract
- Let G be a bipartite graph with bipartition (X, Y). An X-interval coloring of G is a proper edge-coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int)(G, X) the minimum k such that G has an X-interval coloring with k colors. In this paper we give various upper and lower bounds on chi(int)(G, X) in terms of the vertex degrees of G. We also determine chi(int) (G, X) exactly for some classes of bipartite graphs G. Furthermore, we present upper bounds on chi(int) (G, X) for classes of bipartite graphs G with maximum degree Delta(G) at most 9: in particular, if Delta(G) = 4, then chi(int) (G, X) amp;lt;= 6; if Delta(G) = 5, then chi(int) (G, X) amp;lt;= 15; if Delta(G) = 6, then chi(int) (G, X) amp;lt;= 33. (C) 2016 Elsevier B.V. All rights reserved.
|
|
| 28. |
- Casselgren, Carl Johan, et al.
(författare)
-
Restricted extension of sparse partial edge colorings of hypercubes
- 2020
-
Ingår i: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:11
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions. (C) 2020 Elsevier B.V. All rights reserved.
|
|
| 29. |
- Casselgren, Carl Johan, et al.
(författare)
-
Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
- 2018
-
Ingår i: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 341:3, s. 627-637
-
Tidskriftsartikel (refereegranskat)abstract
- An interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. Denote by w(G) (w(c)(G)) and W(G) (W-c(G)) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G, respectively. We present some new sharp bounds on w(G) and W(G) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2-connected multigraph with an interval coloring, then W(G) amp;lt;= 1 + left perpendicular vertical bar V(G)vertical bar/2 right perpendicular (Delta(G) - 1). We also give several results towards the general conjecture that W-c(G) amp;lt;= I vertical bar V(G)vertical bar for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4. (C) 2017 Elsevier B.V. All rights reserved.
|
|
| 30. |
- Casselgren, Carl Johan, 1982-
(författare)
-
Vertex coloring complete multipartite graphs from random lists of size 2
- 2011
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 311:13, s. 1150-1157
-
Tidskriftsartikel (refereegranskat)abstract
- Let Ks×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of Ks×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.
|
|
