Combinatorial Geometry Problems in Pattern Recognition

Abstract. Combinatorial geometry problems motivated by point pattern matching algorithms are considered, and the classical exact matching situation and several variants are discussed.     

Combinatorial Geometry Problems in Pattern Recognition

   Abstract. Combinatorial geometry problems motivated by point pattern matching algorithms are considered, and the classical exact matching situation and several variants are discussed.     

（0,1）矩阵,组合竞赛与Ramsey问题

本文提出用（０，１）矩阵的乘法来研究Ｒａｍｓｅｙ问题，并结合组合竞赛观点给出一大类经典Ｒａｍｓｅｙ数的构造性（算法性）下界。     

Combinatorial Veronese Structures, Their Geometry, and Problems of Embeddability

Finite generalized Veronese spaces of special type (associated with single-line geometry) are studied, and problems concerning embeddability of the resulting configurations are discussed. Received: October 17, 2005. Revised: February 13, 2006.     

A synopsis of Combinatorial Integral Geometry

A Lie coalgebra is a coalgebra whose comultiplication Δ : M → M ? M satisfies the Lie conditions. Just as any algebra A whose multiplication ? : A ? A → A is associative gives rise to an associated Lie algebra $\text{L}$(A), so any coalgebra C whose comultiplication Δ : C → C ? C is associative gives rise to an associated Lie coalgebra $\text{L}$^c(C). The assignment C ? $\text{L}$^c(C) is functorial. A universal coenveloping coalgebra Uc(M) is defined for any Lie Lie coalgebra M by asking for a right adjoint U^c to $\text{L}$^c. This is analogous to defining a universal enveloping algebra U(L) for any Lie algebra L by asking for a left adjoint U to the functor $\text{L}$. In the case of Lie algebras, the unit (i.e., front adjunction) 1 → $\text{L}$ o U of the adjoint functor pair U ? $\text{L}$ is always injective. This follows from the Poincaré-Birkhoff-Witt theorem, and is equivalent to it in characteristic zero (x = 0). It is, therefore, natural to inquire about the counit (i.e., back adjunction) $\text{L}$^c o U^c → 1 of the adjoint functor pair $\text{L}$^c ? U^c.Theorem. For any Lie coalgebra M, the natural map$\text{L}$^c(U^cM) → M is surjective if and only if M is locally finite, (i.e., each element of M lies in a finite dimensional sub Lie coalgebra of M).An example is given of a non locally finite Lie coalgebra. The existence of such an example is surprising since any coalgebra C whose diagonal Δ is associative is necessarily locally finite by a result of that theory. The present paper concludes with a development of an analog of the Poincaré-Birkhoff-Witt theorem for Lie algebras which we choose to call the Dual Poincaré-Birkhoff-Witt Theorem and abbreviate by “The Dual PBWθ.” The constraints of the present paper, however, allow only a sketch of this theorem. A complete proof will appear in a subsequent paper. The reader may, however, consult [12], in the meantime, for details. The Dual PBWθ shows for any locally finite Lie coalgebra M the existence (in χ = 0) of a natural isomorphism of the graded Hopf algebras ₀E(U^cM) and ₀E(S^cM) associated to U^cM and to S^cM = U^c(TrivM) when U^c(M) and S^c(M) are given the Lie filtrations. [Just as U^c(M) is the analog of the enveloping algebra U(L) of a Lie algebra L, so S^c(V) is the analog of the symmetric algebra S(V) on a vector space V. Triv(M) denotes the trivial Lie coalgebra structure on the underlying vector space of M obtained by taking the comultiplication to be the zero map.]     

Combinatorial Problems in Infinite Spaces

Several combinatorial problems in finite projective spaces which are rather hard to be solved, are unexpectedly easy in infinite spaces. In this paper, we deal with this question and more generally in linear spaces.     

Some Low Distortion Metric Ramsey Problems

In this note we consider the metric Ramsey problem for the normed spaces $\ell_p$. Namely, given some $1\le p \le \infty$ and $\alpha \ge 1$, and an integer $n$, we ask for the largest $m$ such that every $n$-point metric space contains an $m$-point subspace which embeds into $\ell_p$ with distortion at most $ \alpha$. In [1] it is shown that in the case of $\ell_2$, the dependence of $m$ on $\alpha$ undergoes a phase transition at $\alpha =2$. Here we consider this problem for other $\ell_p$, and specifically the occurrence of a phase transition for $p\neq 2$. It is shown that a phase transition does occur at $\alpha=2$ for every $p\in [1,2]$. For $p > 2$ we are unable to determine the answer, but estimates are provided for the possible location of such a phase transition. We also study the analogous problem for isometric embedding and show that for every $1 < p < \infty$ there are arbitrarily large metric spaces, no four points of which embed isometrically in $\ell_p$.     

Combinatorial Optimization Problems in Ultrametric Spaces

We study the solutions of some known combinatorial optimization problems including the minimum matching problem, the minimum spanning tree problem, and the traveling salesman problem in d-dimensional p-adic spaces. It appears that the greedy algorithms yield the optimal solutions of these problems in the ultrametric space, which allows obtaining explicit expressions for the estimates of their averages. We study the asymptotic behavior of these averages as the number of points increases infinitely and find some similarities to the Euclidean case, as well as new, unexpected properties.     

On Ramsey numbers of fans

It is shown that r(F₂,F_n)=4n+1 for n≥2, and r(F_s,F_n)≤4n+2s for n≥s≥2.     

On Geometric Graph Ramsey Numbers

For any two-colouring of the segments determined by 3n − 3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing cycle of length n in the second colour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings in multicoloured geometric graphs. Research partially supported by Hungarian Scientific Research Grants OTKA T043631 and NK67867.     

Some Problems in Nonclassical Algebraic Geometry

We describe the general approach to a nonstandard geometry with the emphasis on associative algebras.     

About Tracing Problems in Dynamic Geometry

Dynamic Geometry is the field of interactively performing geometric construction on a computer. In addition to simulating ruler-and-compass constructions we allow a drag mode. This drag mode allows to move geometric objects that have at least one degree of freedom. The remaining part of the construction should adjust automatically. Thus, during the motion, we have to trace the resulting paths of all geometric objects. This path tracking problem is known as the Tracing Problem from Dynamic Geometry. It combines the step-by-step procedure of doing geometric constructions with the continuous concept of motions. This study is based on the model for Dynamic Geometry used in the interactive geometry software Cinderella. We give a numerical solution to the Tracing Problem based on continuation methods and a reliable algorithm based on real and complex interval arithmetic. Degenerate situations like the intersection of two identical lines lead to critical points in the configuration space and are treated separately.     

Problems of Lifts in Symplectic Geometry

Let(M,ω)be a symplectic manifold.In this paper,the authors consider the notions of musical(bemolle and diesis)isomorphisms ω~b:T M→T~*M and ω~?:T~*M→TM between tangent and cotangent bundles.The authors prove that the complete lifts of symplectic vector field to tangent and cotangent bundles is ω~b-related.As consequence of analyze of connections between the complete lift ~cω_(T M )of symplectic 2-form ω to tangent bundle and the natural symplectic 2-form dp on cotangent bundle,the authors proved that dp is a pullback o f~cω_(TM)by ω~?.Also,the authors investigate the complete lift ~cφ_T~*_M )of almost complex structure φ to cotangent bundle and prove that it is a transform by ω~?of complete lift~cφ_(T M )to tangent bundle if the triple(M,ω,φ)is an almost holomorphic A-manifold.The transform of complete lifts of vector-valued 2-form is also studied.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

On Ramsey numbers for circuits

Denote by r_k(n) the largest integer for which there exists some way of coloring the edges of a complete graph on r_k(n) vertices in k colors without forcing the appearance of a monochromatic simple circuit of length n. A new lower bound for r_k(5) is obtained.     

On Combinatorial Cubes

A sequence of positive integers with positive lower density contains a Hilbert (or combinatorial) cube size c log log n up to n. We prove this bound is sharp for some thinner sequence.