| 31. |
- Cutler, Jonathan, et al.
(författare)
-
Unavoidable subgraphs of colored graphs
- 2008
-
Ingår i: Discrete Mathematics. - Amsterdam : Elsevier. - 0012-365X .- 1872-681X. ; 308:19, s. 4396-4413
-
Tidskriftsartikel (refereegranskat)abstract
- A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper. we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let y(k) be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K-k/2's or simply one K-k/2. Bollobas conjectured that for all k and epsilon > 0, there exists an n(k, epsilon) such that if n >= n(k, epsilon) then every two-edge-coloring of K-n, in which the density of each color is at least epsilon, contains a member of this family. We solve this conjecture and present a series of results bounding it (k, s) for different ranges of epsilon. In particular, if epsilon is sufficiently close to 1/2, the gap between out upper and lower bounds for n(k, epsilon) is smaller than those for the classical Ramsey number R(k, k).
|
|
| 32. |
- Dadedzi, Kenneth, et al.
(författare)
-
On the distribution of eigenvalues of increasing trees
- 2024
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 347:2
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that the multiplicity of a fixed eigenvalue alpha in a random recursive tree on n vertices satisfies a central limit theorem with mean and variance asymptotically equal to mu alpha n and sigma alpha 2n respectively. It is also shown that mu alpha and sigma alpha 2 are positive for every totally real algebraic integer. The proofs are based on a general result on additive tree functionals due to Holmgren and Janson. In the case of the eigenvalue 0, the constants mu 0 and sigma 02 can be determined explicitly by means of generating functions. Analogous results are also obtained for Laplacian eigenvalues and binary increasing trees.
|
|
| 33. |
- Engström, Alexander
(författare)
-
Complexes of directed trees and independence complexes
- 2009
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 309:10, s. 3299-3309
-
Tidskriftsartikel (refereegranskat)abstract
- First we prove that certain complexes on directed acyclic graphs are shellable. Then we study independence complexes. Two theorems used for breaking and gluing such complexes are proved and applied to generalize the results by Kozlov.An interesting special case is anti-Rips complexes: a subset P of a metric space is the vertex set of the complex, and we include as a simplex each subset of P with no pair of points within distance r. For any finite subset P of R the homotopy type of the anti-Rips complex is determined.
|
|
| 34. |
- Eriksen, Niklas, 1974-
(författare)
-
Expected number of inversions after a sequence of random adjacent transpositions : an exact expression
- 2005
-
Ingår i: Discrete Mathematics. - Amsterdam, Netherlands : Elsevier. - 0012-365X .- 1872-681X. ; 298, s. 155-168
-
Tidskriftsartikel (refereegranskat)abstract
- A formula for calculating the expected number of inversions after t random adjacent transpositions has been presented by Eriksson et al. We have improved their result by determining a formula for the unknown integer sequence d_r that was used in their formula and also made the formula valid for large t.
|
|
| 35. |
- 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)
|
|
| 36. |
- Fleischner, Herbert, et al.
(författare)
-
Circuit double covers in special types of cubic graphs
- 2009
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 309:18, s. 5724-5728
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers.
|
|
| 37. |
- Fleischner, Herbert, et al.
(författare)
-
Cycle double covers containing certain circuits in cubic graphs having special structures
- 2015
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 338:10, s. 1750-1754
-
Tidskriftsartikel (refereegranskat)abstract
- Our point of departure is Fleischner and Haggkvist (2014, Theorem 2). We first generalize this theorem. Then we apply it to cubic graphs whose vertex set can be decomposed into two classes, one class inducing a circuit and the other class inducing a (subdivision of a) caterpillar. (C) 2014 Elsevier B.V. All rights reserved.
|
|
| 38. |
- Glazik, Christian, et al.
(författare)
-
Bounds for the Static Permutation Mastermind game
- 2021
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 344:3
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper' we introduce a variant of Mastermind, which we call Static Permutation Mastermind and which is defined as follows. One player creates a secret code, called secret, consisting of n colors on n pegs, where each color is used exactly once. The second player tries to determine the secret with as few questions as possible, where each question is a possible secret and all questions are asked at once. After having asked all questions, he receives for each question the number of correctly placed colors and has one more try to determine the secret. The main result of this paper is an upper bound of O(n1.525) questions. It is proved by a distinction of pairs of possible secrets with low and high Hamming distance. For pairs with a low Hamming distance we construct questions using certain arithmetic progressions. For pairs with a high Hamming distance we estimate the size of a vertex cover in a suitable hypergraph. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of Ω(nlogn).
|
|
| 39. |
- Goodman, O., et al.
(författare)
-
On the tight span of an antipodal graph
- 2000
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 218:1-3, s. 73-96
-
Tidskriftsartikel (refereegranskat)abstract
- The tight span of a finite metric space is essentially the 'smallest' path geodesic space into which the metric space embeds isometrically. In this situation, the tight span is also contractible and has a natural cell structure, so that it lends itself naturally to the study of the Cayley graph of a group. As a first step in this study, we consider the tight span of a metric space which arises from the graph metric of an antipodal graph. In particular, we develop techniques for the study of the tight span of a graph, which we then apply to antipodal graphs. In this way, we are able to find the polytopal structure of the tight span for special examples of antipodal graphs. Finally, we present computer generated examples of tight spans which were made possible by the techniques developed in this paper. (C) 2000 Elsevier Science B.V. All rights reserved.
|
|
| 40. |
- Gordeev, Alexey
(författare)
-
Combinatorial Nullstellensatz and Turán numbers of complete r-partite r-uniform hypergraphs
- 2024
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 347:7
-
Tidskriftsartikel (refereegranskat)abstract
- In this note we describe how Lasoń's generalization of Alon's Combinatorial Nullstellensatz gives a framework for constructing lower bounds on the Turán number ex(n,Ks1,…,sr(r)) of the complete r-partite r-uniform hypergraph Ks1,…,sr(r). To illustrate the potential of this method, we give a short and simple explicit construction for the Erdős box problem, showing that ex(n,K2,…,2(r))=Ω(nr−1/r), which asymptotically matches best known bounds when r≤4.
|
|
