共查询到20条相似文献,搜索用时 15 毫秒
1.
V. A. Koshelev 《Mathematical Notes》2010,87(3-4):537-542
The following problem of combinatorial geometry is considered. Given positive integers n and q, find or estimate a minimal number h for which any set of h points in general position in the plane contains n vertices of a convex polygon for which the number of interior points is divisible by q. For a wide range of parameters, the existing bound for h is dramatically improved. 相似文献
2.
The paper is devoted to selected problems of combinatorial geometry.
相似文献3.
In this paper new proofs of the Canonical Ramsey Theorem, which originally has been proved by Erd?s and Rado, are given. These yield improvements over the known bounds for the arising Erd?s-Rado numbersER(k; l), where the numbersER(k; l) are defined as the least positive integern such that for every partition of thek-element subsets of a totally orderedn-element setX into an arbitrary number of classes there exists anl-element subsetY ofX, such that the set ofk-element subsets ofY is partitioned canonically (in the sense of Erd?s and Rado). In particular, it is shown that $$2^{c1} .l^2 \leqslant ER(2;l) \leqslant 2^{c_2 .l^2 .\log l} $$ for every positive integerl≥3, wherec 1,c 2 are positive constants. Moreover, new bounds, lower and upper, for the numbersER(k; l) for arbitrary positive integersk, l are given. 相似文献
4.
5.
David J. Grynkiewicz 《Combinatorica》2006,26(4):445-453
An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct so that they can be considered
as sets. If S is a sequence of m+n−1 elements from a finite abelian group G of order m and exponent k, and if
is a sequence of integers whose sum is zero modulo k, then there exists a rearranged subsequence
of S such that
. This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when m = n and wi = 1 for all i, and confirms a conjecture of Y. Caro. Furthermore, we in part verify a related conjecture of Y. Hamidoune, by showing that
if S has an n-set partition A=A1, . . .,An such that |wiAi| = |Ai| for all i, then there exists a nontrivial subgroup H of G and an n-set partition A′ =A′1, . . .,A′n of S such that
and
for all i, where wiAi={wiai |ai∈Ai}. 相似文献
6.
Given integers , the th power of the path is the ordered graph with vertex set and all edges of the form where . The Ramsey number is the minimum such that every 2-coloring of results in a monochromatic copy of . It is well-known that . For , Balko–Cibulka–Král–Kynčl proved that and asked for the growth rate for fixed . When , we improve this upper bound substantially by proving . Using this result, we determine the correct tower growth rate of the -uniform hypergraph Ramsey number of a -clique versus an ordered tight path. Finally, we consider an ordered version of the classical Erdős–Hajnal hypergraph Ramsey problem, improve the tower height given by the trivial upper bound, and conjecture that this tower height is optimal. 相似文献
7.
Zhong Gen Su 《数学学报(英文版)》2011,27(8):1573-1580
Let π be a minimal Erdös-Szekeres permutation of 1, 2, ..., n 2, and let l n,k be the length of the longest increasing subsequence in the segment (π(1), ..., π(k)). Under uniform measure we establish an exponentially decaying bound of the upper tail probability for l n,k , and as a consequence we obtain a complete convergence, which is an improvement of Romik’s recent result. We also give a precise lower exponential tail for l n,k . 相似文献
8.
Let s≥2 be an integer. Denote by f 1(s) the least integer so that every integer l>f 1(s) is the sum of s distinct primes. Erd?s proved that f 1(s)<p 1+p 2+?+p s +Cslogs, where p i is the ith prime and C is an absolute constant. In this paper, we prove that f 1(s)=p 1+p 2+?+p s +(1+o(1))slogs=p 2+p 3+?+p s+1+o(slogs). This answers a question posed by P. Erd?s. 相似文献
9.
Suda (2012) extended the Erds-Ko-Rado theorem to designs in strongly regularized semilattices.In this paper we generalize Suda’s results in regularized semilattices and partition regularized semilattices,give many examples for these semilattices and obtain their intersection theorems. 相似文献
10.
11.
12.
Paul Erdős proposed the following graph game. Starting with the empty graph on n vertices, two players, Trailmaker and Breaker, draw edges alternatingly. Each edge drawn has to start at the endpoint of
the previously drawn edge, so the sequence of edges defines a trail. The game ends when it is impossible to continue the trail,
and Trailmaker wins if the trail is eulerian. For all values of n, we determine which player has a winning strategy.
Received: November 6, 1996 / Revised: May 2, 1997 相似文献
13.
14.
J. Korevaar 《Combinatorica》2001,21(2):239-250
Dedicated to the memory of Paul Erdős
In connection with the elementary proof of the prime number theorem, Erdős obtained a striking quadratic Tauberian theorem
for sequences. Somewhat later, Siegel indicated in a letter how a powerful "fundamental relation" could be used to simplify
the difficult combinatorial proof. Here the author presents his version of the (unpublished) Erdős–Siegel proof. Related Tauberian
results by the author are described.
Received December 20, 1999 相似文献
15.
Every Polish group is not free whereas some F σ group may be free. Also, every automorphism group of a structure of cardinality, e.g. ℶ ω , is not free. 相似文献
16.
17.
The Erdös-Szekeres convexn-gon theorem states that for anyn3, there is a smallest integerf(n) such that any set of at leastf(n) points in the planeE
2, no three collinear, contains the vertices of a convexn-gon. We consider three versions of this result as applied to convexly independent points and convex polytopes inE
d
>,d2. 相似文献
18.
Let \(\mathcal{S}\) be a finite additively written commutative semigroup, and let \(\exp(\mathcal{S})\) be its exponent which is defined as the least common multiple of all periods of the elements in \(\mathcal{S}\) . For every sequence T of elements in \(\mathcal{S}\) (repetition allowed), let \(\sigma(T) \in\mathcal{S}\) denote the sum of all terms of T. Define the Davenport constant \(\mathsf{D}(\mathcal{S})\) of \(\mathcal{S}\) to be the least positive integer d such that every sequence T over \(\mathcal{S}\) of length at least d contains a proper subsequence T′ with σ(T′)=σ(T), and define \(\mathsf{E}(\mathcal{S})\) to be the least positive integer ? such that every sequence T over \(\mathcal{S}\) of length at least ? contains a subsequence T′ with \(|T|-|T'|= \lceil\frac{|\mathcal{S}|}{\exp(\mathcal{S})} \rceil \exp(\mathcal{S})\) and σ(T′)=σ(T). When \(\mathcal{S}\) is a finite abelian group, it is well known that \(\lceil\frac{|\mathcal{S}|}{\exp(\mathcal{S})} \rceil\exp (\mathcal{S})=|\mathcal{S}|\) and \(\mathsf{E}(\mathcal{S})=\mathsf{D}(\mathcal{S})+|\mathcal{S}|-1\) . In this paper we investigate whether \(\mathsf{E}(\mathcal{S})\leq \mathsf{D}(\mathcal{S})+ \lceil\frac{|\mathcal{S}|}{\exp(\mathcal {S})} \rceil \exp(\mathcal{S})-1\) holds true for all finite commutative semigroups \(\mathcal{S}\) . We provide a positive answer to the question above for some classes of finite commutative semigroups, including group-free semigroups, elementary semigroups, and archimedean semigroups with certain constraints. 相似文献
19.
According to the Erd?s–Szekeres theorem, for every n, a sufficiently large set of points in general position in the plane contains n in convex position. In this note we investigate the line version of this result, that is, we want to find n lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains n in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd?s–Szekeres theorem. 相似文献
20.
Solving a problem of Erdős and Heilbronn, in 1994 Dias da Silva and Hamidoune proved that ifA is a set ofk residues modulo a primep,p≥2k−3, then the number of different elements of ℤ/pℤ that can be written in the forma+a′ wherea, a′ ∈A,a∈a′, is at least 2k−3. Here we extend this result to arbitrary Abelian groups in which the order of any nonzero element is at least 2k−3.
Visiting the Rényi Institute of the Hungarian Academy of Sciences. Research partially supported by Hungarian Scientific Research
Grants OTKA T043623 and T043631 and the CRM, University of Montreal. 相似文献