EuDML | Browse

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 25

A De Bruijn-Erdős theorem for $1$ - $2$ metric spaces

Václav Chvátal (2014)

Czechoslovak Mathematical Journal

A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces where each nonzero distance equals $1$ or $2$ .

A general upper bound in extremal theory of sequences

Martin Klazar (1992)

Commentationes Mathematicae Universitatis Carolinae

We investigate the extremal function $f (u, n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v = a_{1} a_{2} . . . a_{m}$ of integers such that 1) $1 \leq a_{i} \leq n$ , 2) $a_{i} = a_{j}, i \neq j$ implies $| i - j | \geq k$ and 3) $v$ contains no subsequence of the type $u$ . We prove that $f (u, n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that $f (u, n) = O (n 2^{O (α {(n)}^{| u | - 4})}) .$ Here $| u |$ is the length of $u$ and $α (n)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions.

M. Sharir (1994)

Discrete & computational geometry

An extremal theorem in the hypercube.

Conlon, David (2010)

The Electronic Journal of Combinatorics [electronic only]

Antichains on three levels.

Lieby, Paulette (2004)

The Electronic Journal of Combinatorics [electronic only]

Arithmetic progressions of length three in subsets of a random set

Yoshiharu Kohayakawa, Tomasz Łuczak, Vojtěch Rödl (1996)

Acta Arithmetica

Baron Münchhausen redeems himself: bounds for a coin-weighing puzzle.

Khovanova, Tanya, Lewis, Joel Brewster (2011)

The Electronic Journal of Combinatorics [electronic only]

Cardinality of height function’s range in case of maximally many rectangular islands - computed by cuts

Eszter Horváth, Branimir Šešelja, Andreja Tepavčević (2013)

Open Mathematics

We deal with rectangular m×n boards of square cells, using the cut technics of the height function. We investigate combinatorial properties of this function, and in particular we give lower and upper bounds for the number of essentially different cuts. This number turns out to be the cardinality of the height function’s range, in case the height function has maximally many rectangular islands.

Codes that attain minimum distance in every possible direction

Gyula Katona, Attila Sali, Klaus-Dieter Schewe (2008)

Open Mathematics

The following problem motivated by investigation of databases is studied. Let $𝒞$ be a q-ary code of length n with the properties that $𝒞$ has minimum distance at least n − k + 1, and for any set of k − 1 coordinates there exist two codewords that agree exactly there. Let f(q, k)be the maximum n for which such a code exists. f(q, k)is bounded by linear functions of k and q, and the exact values for special k and qare determined.