| 61. |
- Koolen, Jack H., et al.
(författare)
-
Injective optimal realizations of finite metric spaces
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:10, s. 1602-1610
-
Tidskriftsartikel (refereegranskat)abstract
- A realization of a finite metric space (X, d) is a weighted graph (G, w) whose vertex set contains X such that the distances between the elements of X in G correspond to those given by d. Such a realization is called optimal if it has minimal total edge weight. Optimal realizations have applications in fields such as phylogenetics, psychology, compression software and Internet tomography. Given an optimal realization (G, w) of (X, d), there always exist certain "proper" maps from the vertex set of G into the so-called tight span of d. In [A. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. Math. 53 (1984) 321-402], Dress conjectured that any such map must be injective. Although this conjecture was recently disproven, in this paper we show that it is possible to characterize those optimal realizations (G, w) for which certain generalizations of proper maps - that map the geometric realization of (G, w) into the tight span instead of its vertex set - must always be injective. We also prove that these "injective" optimal realizations always exist, and show how they may be constructed from non-injective ones. Ultimately it is hoped that these results will contribute towards developing new ways to compute optimal realizations from tight spans.
|
|
| 62. |
- Laksman, Efraim, et al.
(författare)
-
Improving bounds on the minimum Euclidean distance for block codes by inner distance measure optimization
- 2010
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 310:22 Special issue SI, s. 3267-3275
-
Tidskriftsartikel (refereegranskat)abstract
- The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size | C |. For q = 8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean. The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q = 8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and | C |. This is true for many multilevel codes.
|
|
| 63. |
- Lehmann, Juliane, et al.
(författare)
-
Some necessary conditions for vector space partitions
- 2012
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:2, s. 351-361
-
Tidskriftsartikel (refereegranskat)abstract
- Some new necessary conditions for the existence of vector space partitions are derived. They are applied to the problem of finding the maximum number of spaces of dimension t in a vector space partition of V(2t, q) that contains m(d) spaces of dimension d, where t/2 < d < t, and also spaces of other dimensions. It is also discussed how this problem is related to maximal partial t-spreads in V (2t, q). We also give a lower bound for the number of spaces in a vector space partition and verify that this bound is tight.
|
|
| 64. |
- Markström, Klas
(författare)
-
Even cycle decompositions of 4-regular graphs and line graphs
- 2012
-
Ingår i: Discrete Mathematics. - Amsterdam : Elsevier BV. - 0012-365X .- 1872-681X. ; 312:17, s. 2676-2681
-
Tidskriftsartikel (refereegranskat)abstract
- An even cycle decomposition of a graph is a partition of its edge into even cycles. We first give some results on the existence of even cycle decomposition in general 4-regular graphs, showing that K 5 is not the only graph in this class without such a decomposition. Motivated by connections to the cycle double cover conjecture we go on to consider even cycle decompositions of line graphs of 2-connected cubic graphs. We conjecture that in this class even cycle decompositions always exists and prove the conjecture for cubic graphs with oddness at most 2. We also discuss even cycle double covers of cubic graphs.
|
|
| 65. |
- Markström, Klas
(författare)
-
Extremal hypergraphs and bounds for the Turan density of the 4-uniform K-5
- 2009
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 309:16, s. 5231-5234
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we find, for n <= 16, the maximum number of edges in a 4-uniform hypergraph which does not have the complete 4-uniform hypergraph on five vertices, K-5(4), as a subgraph. Equivalently, we find all optimal (n, n-4, n-5) covering designs for n <= 16. Using these results we find a new upper bound for the Turin density of K-5(4). pi(K-5(4)) <= 1753/2380 = 0.73655.... Finally we make some notes on the structure of the extremal 4-graphs for this problem and the conjectured extremal family. (C) 2009 Published by Elsevier B.V.
|
|
| 66. |
- Nordh, Gustav
(författare)
-
Perfect Skolem sets
- 2008
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 308:9, s. 1653-1664
-
Tidskriftsartikel (refereegranskat)abstract
- A Skolem sequence is a sequence s1, s2, ..., s2 n (where si ? A = { 1, ..., n }), each si occurs exactly twice in the sequence and the two occurrences are exactly si positions apart. A set A that can be used to construct Skolem sequences is called a Skolem set. The problem of deciding which sets of the form A = { 1, ..., n } are Skolem sets was solved by Thoralf Skolem in the late 1950s. We study the natural generalization where A is allowed to be any set of n positive integers. We give necessary conditions for the existence of Skolem sets of this generalized form. We conjecture these necessary conditions to be sufficient, and give computational evidence in favor of our conjecture. We investigate special cases of the conjecture and prove that the conjecture holds for some of them. We also study enumerative questions and show that this problem has strong connections with problems related to permutation displacements. © 2007 Elsevier B.V. All rights reserved.
|
|
| 67. |
|
|
| 68. |
- Panja, Avijit, et al.
(författare)
-
Some matroids related to sum-rank metric codes
- 2023
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 346:4
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce the notion of sum-matroids and show its association with sum-rank metric codes. As a consequence, some results for sum-rank metric codes by Martínez-Peñas are generalized for sum-matroids. The sum-matroids generalize the notions of matroids and q-matroids. We define the generalized weights for sum-matroids and prove a Wei-type duality theorem which generalizes the analogous cases for matroids and q-matroids.
|
|
| 69. |
- Pasticci, Fabio, et al.
(författare)
-
On rank and kernel of some mixed perfect codes
- 2009
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 309:9, s. 2763-2774
-
Tidskriftsartikel (refereegranskat)abstract
- Mixed perfect 1-error correcting codes and the associated dual codes over the group Z (n, l), Z (n, l) = under(under(Z2 × Z2 × ⋯ × Z2, {presentation form for vertical right curly bracket}), n) × underover(Z, 2, l), n ≥ 1 and l ≥ 2, are investigated. A lower and an upper bound for the rank k of the kernel of mixed perfect 1-error correcting codes in Z (n, l), depending on the rank r of the mixed perfect code and the structure of the corresponding dual code, are given. Due to a general construction of mixed perfect 1-error correcting group codes in Z (n, l), we show that the upper bound is tight for some n, l and r.
|
|
| 70. |
- Sjöstrand, Jonas
(författare)
-
Making multigraphs simple by a sequence of double edge swaps
- 2021
-
Ingår i: Discrete Mathematics. - : Elsevier B.V.. - 0012-365X .- 1872-681X. ; 344:5
-
Tidskriftsartikel (refereegranskat)abstract
- We show that any loopy multigraph with a graphical degree sequence can be transformed into a simple graph by a finite sequence of double edge swaps with each swap involving at least one loop or multiple edge. Our result answers a question of Janson motivated by random graph theory, and it adds to the rich literature on reachability of double edge swaps with applications in Markov chain Monte Carlo sampling from the uniform distribution of graphs with prescribed degrees.
|
|
