| 1. |
- Asratian, Armen, et al.
(författare)
-
On the number of nearly perfect matchings in almost regular uniform hypergraphs
- 1999
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 207:1, s. 1-8
-
Tidskriftsartikel (refereegranskat)abstract
- Strengthening the result of R dl and Frankl (Europ. J. Combin 6 (1985) 317-326), Pippenger proved the theorem stating the existence of a nearly perfect matching in almost regular uniform hypergraph satisfying some conditions (see J. Combin. Theory A 51 (1989) 24-42). Grable announced in J. Combin. Designs 4 (4) (1996) 255-273 that such hypergraphs have exponentially many nearly perfect matchings. This generalizes the result and the proof in Combinatorica 11 (3) (1991) 207-218 which is based on the R dl Nibble algorithm (European J. Combin. 5 (1985) 69-78). In this paper, we present a simple proof of Grable's extension of Pippenger's theorem. Our proof is based on a comparison of upper and lower bounds of the probability for a random subgraph to have a nearly perfect matching. We use the Lovasz Local Lemma to obtain the desired lower bound of this probability.
|
|
| 2. |
- Asratian, Armen S.
(författare)
-
Some results on an edge coloring problem of Folkman and Fulkerson
- 2000
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 223:1-3, s. 13-25
-
Tidskriftsartikel (refereegranskat)abstract
- In 1968, Folkman and Fulkerson posed the following problem: Let G be a graph and let (n1,...,nt) be a sequence of positive integers. Does there exist a proper edge coloring of G with colors 1,2,...,t such that precisely ni edges receive color i, for each i=1,...,t? If such a coloring exists then the sequence (n1,...,nt) is called color-feasible for G. Some sufficient conditions for a sequence to be color-feasible for a bipartite graph where found by Folkman and Fulkerson, and de Werra. In this paper we give a generalization of their results for bipartite graphs. Furthermore, we find a set of color-feasible sequences for an arbitrary simple graph. In particular, we describe the set of all sequences which are color-feasible for a connected simple graph G with Δ(G)3, where every pair of vertices of degree at least 3 are non-adjacent.
|
|
| 3. |
- Asratian, Armen S., 1951-, et al.
(författare)
-
Stable properties of graphs
- 1991
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 90:2, s. 143-152
-
Tidskriftsartikel (refereegranskat)abstract
- Abstract For many properties P Bondy and Chvátal (1976) have found sufficient conditions such that if a graph G + uv has property P then G itself has property P. In this paper we will give a generalization that will improve ten of these conditions.
|
|
| 4. |
- Bränden, Petter, et al.
(författare)
-
Catalan continued fractions, and increasing subsequences in permutations
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 258:03-jan, s. 275-287
-
Tidskriftsartikel (refereegranskat)abstract
- We call a Stieltjes continued fraction with monic monomial numerators a Catalan continued fraction. Let e(k)(pi) be the number of increasing subsequences of length k + 1 in the permutation pi. We prove that any Catalan continued fraction is the multivariate generating function of a family of statistics on the 132-avoiding permutations, each consisting of a (possibly infinite) linear combination of the e(k)S. Moreover, there is an invertible linear transformation that translates between linear combinations of ekS and the corresponding continued fractions. Some applications are given, one of which relates fountains of coins to 132-avoiding permutations according to number of inversions. Another relates ballot numbers to such permutations according to number of right-to-left maxima.
|
|
| 5. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)abstract
- Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome, It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to [(2n - 2)/3] for n greater than or equal to 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely [(n + 1)/2]. Computations of Bafha and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player's case. Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.
|
|
| 6. |
- Eriksson, K., et al.
(författare)
-
Stable matching in a common generalization of the marriage and assignment models
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 217:3-Jan, s. 135-156
-
Tidskriftsartikel (refereegranskat)abstract
- In the theory of two-sided matching markets there are two well-known models: the marriage model (where no money is involved) and the assignment model (where payments are involved). Roth and Sotomayor, Two-Sided Matching, Cambridge University Press, Cambridge, 1990, asked for an explanation for the similarities in behavior between those two models. We address this question by introducing a common generalization that preserves the two important features: the existence of a stable outcome and the lattice property of the set of stable outcomes.
|
|
| 7. |
- Guibert, O., et al.
(författare)
-
Doubly alternating Baxter permutations are Catalan
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 217:03-jan, s. 157-166
-
Tidskriftsartikel (refereegranskat)abstract
- The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given.
|
|
| 8. |
- Heden, Olof, et al.
(författare)
-
Bruen chains in PG(3, p(k)) k >= 2
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 214:3-Jan, s. 251-253
-
Tidskriftsartikel (refereegranskat)abstract
- The Bruen chains of PC(3,q) for q = 9, 25 and 27 are described. They were found by a computer search. In the case q = 49 no chains have been found yet.
|
|
| 9. |
- Heden, Olof
(författare)
-
Maximal partial spreads and the modular n-queen problem III
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 243:3-Jan, s. 135-150
-
Tidskriftsartikel (refereegranskat)abstract
- Maximal partial spreads in PG(3, q) q = p(k), p odd prime and q greater than or equal to 7, are constructed for any integer n in the interval (q(2) + 1)/2 + 6 less than or equal to n less than or equal to (5q(2) + 4q - 1)/8 in the case q + 1 0, +/-2, +/-4, +/-6, +/-10, 12 (mod 24). In all these cases. maximal partial spreads of the size (q(2) + 2 + n have also been constructed for some small values of the integer n. These values depend on q and are mainly n = 3 and n = 4. Combining these results with previous results of the author and with that of others we can conclude that there exist maximal partial spreads in PG(3, q), q = p(k) where p is an odd prime and q greater than or equal to 7, of size n for any integer n in the interval (q(2) + 1) /2 + 6 less than or equal to n less than or equal to q(2) - q + 2.
|
|
| 10. |
- Heden, Olof
(författare)
-
On the reconstruction of perfect codes
- 2002
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 256:2-Jan, s. 479-485
-
Tidskriftsartikel (refereegranskat)abstract
- We show how to reconstruct a perfect I-error correcting binary code of length n from the code words of weight (n + 1)/2.
|
|
