PARTICLES                                                         Jabbarkhanov Khumoyun

428 

 

and undirected, connected graph. Since the definition of these graphs is not our main concern, we are not dwell 

on them. 

  a)   

  b) 

 

 

 Fig.2

 

graphs with different degrees of the vertices. [2,3]

 

Definition  2.Let  G  be  an  undirected  graph  or  multigraph.For  each  vertex  v  of  G,  the  degree  of    v,written 

deg(v),is the number of edges in G that the incident with v. Here loop of the vertex v is considered as two 

incident edges for v.For example in fig.2(a)     deg(v

1

)=1,deg(v

2

)=2,deg(v

5

)=5. 

Theorem 1.If G   is undirected graph or multigraph ,then 

         

         ∑

deg(??????) = 2|??????|

??????∈??????

                                                                                          (1)  [4] 

“Proof. As we consider each edge {a, b}  in graph G .we find that the edge contributes a count of 1  to each 

of deg(a),deg(b)      and consequently  a count of 2     ∑

deg (??????)

??????∈??????

. Thus     

2|??????|     accounts for deg(v),for 

all   v

∈ ??????  and    ∑

deg(??????) = 2|??????|

??????∈??????

’’ [1]. 

 For example in fig.3(b) graph has a sum of the degrees of all vertices is equal to 16, so 16=

2|??????|      |??????|=8. 

That is, we have 8 edges . Now we present the famous theorem  

Definition 3.A complete graph is a graph with n vertices and an edge  between every two vertices. There are 

no loops.

 

Usually, they are denoted by  K

n 

(see fig.3).

 

Where n denotes the number of vertices

 

Since we are 

interested in the structure, we will work with complete graphs. All of the following theorems and conclusions 

will be shown relatively complete graphs 

 

 Fig.3 Complete graphs.[5] 

We leave the reader to definition the Euler trail and circuit. 

Theorem 2.A connected and undirected or multigraph  G is Euler circuit  if and only if G is connected and 

every vertex has an even degree. 

Follows from this theorem: 

Proposition 1. We can construct Euler trail if and only if it has exactly two vertices of odd degree.[2] 

429 

 

Proof. Let G=(V,E) is a subgraph and it passes all the edges.

 

Has at the same time even degree of each vertex.

 

Their vertices are denoted by v

1

,

 

v

2

,v

3

…v

n

.

 

We denote v

1

 as initial vertex of the circuit.

 

As the circuit comes 

back to the v

1

 while having an even degree of each vertex.

 

Connection with any vertex v

1

 doing two vertices 

of odd degree.

 

Such compounds edges vertices v

1

 and v

2

 .

 

So we've got two vertices of odd degree and all the 

rest will be even. 

Proposition 2.

 

Euler circuit is the longest circuit  in a complete graph.[6]                                                                         

Proposition 3. Euler trail is the longest trail  in a complete graph.[7] 

We must try to determine the maximum length(L

c

) of circuit in K

n.

 

Let  n  be  an  odd  number.

 

Then  we  know  that  the  degree  of  each  vertex  is  equal  to  n-1  which  is  even.

 

By 

Theorem 2 we know that Euler circuit(which is the maximum length of circuit)  is performed when all vertices 

have even degree.

 

So our cycle pass all edge of the graph.

 

We just need to determine the number of edges of 

this graph.

 

Using (1) 

n(n-1)=2|

??????|

,

     |??????| =

??????(??????−1)

2

       so  ,when n is odd number  

                      L

c

=

??????(??????−1)

2

 

Now let n be an even number.

 

Then each vertex will have odd degree (n-1).

 

To make their numbers even 

remove the edges {v

1

,v

2

},{v

3

,v

4

},{v

5,

v

6

}…{v

n-1

,v

n

}(see Fig.4) 

           

          Fig.4 Complete graph.

 

Here shows us the necessary edges to understand well

 

So we have removed   

??????

2

 

   

edges.

 

In fact, it is not important to remove this order.

 

Main aim is to make the 

degree of all vertices even.

 

So, now the degree of each vertex is equal to n-2 (even). By the (1)  

(n-2)n=2|

??????|

 , 

|??????| =

(??????−2)??????

2

     so,

 

when n is even number 

                           L

c

 =

(??????−2)??????

2

  . 

We can write this as a theorem. 

Theorem 3. The maximum length of the circuit in K

n

 equal to  

L

c

=

??????(??????−1)

2

 (when n is odd number)  (2)             and               L

 

c

=

(??????−2)??????

2

  (when n is even number). (3) 

For example maximum length of the circuit in  K

6 

 equal to L

c

=

(6−2)6

2

= 12. 

430 

 

Using Proposition 1, we can solve the following problem.

 

How to determine maximum length of the trail(L

t

) 

in K

n

? 

Let n be an even number. Following the the last problem we remove edges {v

3

,v

4

},{v

5,

v

6

}…{v

n1

,v

n

}.(see 

Fig.4)

 

We leave only one edge and let it be

 

{v

1

,v

2

}.So, we create the conditions in the Proposition of 1.

 

Because we have v

1

 and v

2

 having odd degree and all other that have even degree. By the (1) we know that 

the total number of edges in K

n

 is equal to |

??????| =

(??????−2)??????

2

. 

We also know that we have removed (

??????

2

− 1) edges.

 

If we take their difference 

(??????−1)??????

2

−(

??????

2

− 1),

 

we obtain the desired result L

t

=

1

2

(n

2

-2n+2),where n is even . 

Now let n be an odd number.

 

Then we get all the vertices of even 

 

and we have to remove only one vertex.

 

Eventually we will get 

??????(??????−1)

2

− 1 edges .So,

 

we get L

t=

1

2

(n

2

-n-2

) where n is odd.

 

Now we write it as a 

theorem. 

Theorem 4. The maximum length of the trail in K

n

 equal to  

L

t=

1

2

(n

2

-n-2

) (when n is odd number)   (4)          and         L

t

=

1

2

(n

2

-2n+2)(when n is even number).(5) 

So, we looked at the needed component of the graph. 

3.

 

Use graphs of various structures 

Now we give some examples of the use of graphs.

 

One of the simple example is the structure of quartz.(see 

Fig.5) 

                     

  

Fig.5

 

Quartz structures that is in the science as equal                                     Fig.6 Structure of some atoms 

Now, we have a simple way we can count the number of edges, because we know the degrees of all vertices. 

By the (1)  |

??????| =

12∗3

2

= 18

.

 

we consider the structure of the atom(Fig.6) as K

8

.

 

If we need to calculate the 

maximum  length  of  circuit,  by  the    formula  (3)  we  can  calculate  L

c

=

6∗8

2

= 24 .By  the  formula  (4)    

L

t

=

1

2

(64 − 8 − 2) = 27     we  calculated the maximum  length of  a trail.

 

It was the most simple examples.

 

In science, much more difficult.

 

Number and length which we used can  help defining the properties 

Concluding 

So, we were able to apply the laws of graph theory in science as physics and chemistry. 

431 

 

 

Referencing  

 [1]. A.V Cherednikova, I.V Zemlyakova (2011). Introduction to graph theory.Kostroma State 

Technological University 

[2].Ralph P.Grimaldi(2003). Discret and combinatorial mathematics.Rose-Hulman Institute of Technology  

[3].

 

Edward A. Bender S. Gill  Williamson (2010). Lists, Decisions and Graphs Retrieved from:

 

chrome-

extension://oemmndcbldboiebfnladdacbdfmadadm/http://cseweb.ucsd.edu/~gill/BWLectSite/Resources/C2

U4GT.pdf   

[4] Paul Van Doore.(2009)Graph Theory and Application.University catholique de Louvain.  

[5]. Keijo Ruohonen (2013) .Graph theory. Retrieved from:

 

chrome-

extension://oemmndcbldboiebfnladdacbdfmadadm/http://math.tut.fi/~ruohonen/GT_English.pdf 

 [6]. Reinhard  Diestel(2000). Graph Theory. Springer-Verlag New York  

[7]. Introduction to Graph Theory Allen Dickson  2006  Retrieved from: chrome-

extension://oemmndcbldboiebfnladdacbdfmadadm/http://www.math.utah.edu/mathcircle/notes/MC_Graph_

Theory.pdf 

[3].

 

Edward A. Bender S. Gill  Williamson (2010). Lists, Decisions and Graphs Retrieved from:

 

chrome-

extension://oemmndcbldboiebfnladdacbdfmadadm/http://cseweb.ucsd.edu/~gill/BWLectSite/Resources/C2

U4GT.pdf   

 

UDK  510.67 

DEFINABILITY OF 2-TYPES IN WEAKLY O-MINIMAL THEORIES 

Biyarova N. B. 

Suleyman Demirel University 

Annotation 

This  article about  "Definability of 2-types in  weakly  o-minimal  theories"    by Biyarova Nazira. 

This paper describes and compares the properties of various kinds of orthogonality, non-orthogonality 

and definability of the 1-types in weakly o-minimal theories, which is one of the classes in the dependent 

theories and presumes the conditions for constructing definability of the 2-type in weakly o-minimal 

theories.  

 

ТҮЙІН 

Берілген мақала “Әлсіз о-минималды теориялардағы  2-типтің анықталымдылығы”. Мұнда 

ортогоналдылық, ортогоналдылық еместік және, тәуелді теорияның бір бөлігі болап табылатын, 

әлсіз о-минималды теориялардағы  1-типтің анықталымдылық қасиеттерін сипаттайды, сонымен 

қатар,  әлсіз о-минималды теориялардағы  2-типтің анықталымдылығы орындалу үшін қажетті 

шартты қарастырады. 

 

 

      The  objective  of  the  thesis  is  to  research  and  compare  the  properties  of  various  kinds  of 

orthogonality,  non-orthogonality  and  definability  of  the  1  and  2-types  in  weakly  o-minimal  theories, 

which is one of the classes in the dependent theories.To find out the conditions to construct definability 

of the 2-type in weakly o-minimal theories. 

        

432 

 

      The  task  of  the  thesis:    To  describe  the  concept  of  orthogonality,  weakly  orthogonality,  almost 

orthogonality  of  the  types  in  weakly  o-minimal  theories.  To  research  the  questions:  would  the  non-

orthogonal  types  be  simultaneously  definable  or  simultaneously  non-definable,  is  it  possible  for  an 

element over the model and a finite set to find non-orthogonal type of the some element over the model. 

This  will help  to  construct  the conditions  on which definability of all 1-types  over the model entails 

definability of the 2-type over the model.  

 

      Scientific novelty and practical significance of the thesis.  

As  S.Shelah  [1]  introduced  the  concept  of  a  stable  theory,  the  fundamental  connection  between 

stable theory and the definability of the types was founded. It is the theory is stable if and only if every 

its type is  definable. After that, it became clear how the definable type is  significant.  But  not  all the 

theories are stable. Any infinite linear order is not stable, i.e. the ordered field of the real numbers doesn’t 

have the stable theory. The surprising fact is noted by van den Dries [2] even though the elementary 

theory of the ordered field of real numbers is unstable, but each type over the set of real numbers is 

definable. Van den Dries’s idea formed the basis of the concept of o-minimality which was introduced 

by A. Pillay and C. Steynhornom [3] a concept that still plays a key role in the modern model theory.  

Realizing  how  important  o-minimality  is,  D.  Marker,  D.  McPherson  and  Charles  Steinhorn 

generalized this concept by means of weakly o-minimal [4]. Linearly ordered structure is called weakly 

o-minimal if any definable subset of it is a finite union of convex sets. They have proved a number of 

interesting  topological  properties  of  weakly  o-minimal  structures  and  real  closed  weakly  o-minimal 

ordered field. But, if every 1-type over a model of weakly o-minimum (dependent) theory is definable 

do from this follow the definability of any type of model? 

       The proposed research has fundamental, theoretical, scientific significance due to their use of 

recent results of mathematical logic (model theory). The research results can be used for further 

research, not only in model theory and algebra, but also in such sections  as Computer Science, as a 

general theory of relational databases and formal methods of software design. 

 

Figure 1: Model theory 

One  of  the  branches  of  Mathematical  logic  is  Model  Theory.  Model  Theory  studies  relationship 

between  semantics  (algebraic  structure)  and  syntax  (formal  language,  language  of  the  first  order 

predicates)  in  other  words  model  theory  studies  algebraic  structures  in  terms  of  mathematical  logic. 

Where a theory is a set of formulas in a particular formal logic and signature, and a model is a structure 

that gives a concrete interpretation of that theory. And the type is consistent set of formulas.  

433 

 

Dedekind  also  defined  the  type  as  a  cut(Dedekind  cut).  There  are  three  kinds  of  cuts:  rational, 

irrational, quasi-rational. And the definability of the types depends on these kinds of cuts. 

The partition (A, B) of a model M is said to be a cut, if A < B. Here A < B means 

⇐⇒ for all a ∈ A 

and for all b 

∈ B (a < b). 

If  either  A  has  a  maximum  element  or  B  has  a  minimum  element, then the cut is called rational 

cut. 

It is said that the cut is quasi-rational if A as well as B are definable.  Non quasi-rational cut is 

called irrational cut.  

Definition 1. It’s  said  that  α

¯ is  weakly  orthogonal  to  the  type  q  if  for  any  A-definable formula 

ψ(x¯, y¯), ψ(x¯, α¯) doesn’t divide q(N ) = ∩θ∈qθ(N ) and denoted as α¯⊥ωq. 

Definition2. It  is said  that  α

¯ isn’t weakly  orthogonal to the  type q  if  there exists A-definable 

formula ψ(x

¯, y

¯)  such that ψ(x

¯, α

¯) divides q(N) (α

¯ ƒ

⊥ω  q). Then p(x) 

∪ q(x) is not complete type. This 

means that their realization does not depend on each other.  More precisely it  means that any pair of 

(α, β) can be moved from one place to another. The r e   a r e  t w o  ki nd s   o f r e a l i z at i on s : 

   a) p(x) 

∪ q(y) ∪ {ϕ(x, y)} 

  b) p(x) 

∪ q(y) ∪{ ¬ϕ(x, y)}.                                                        

       

 

Figure 2: Weakly orthogonality                                                                                  Figure 2: Weakly non-orthogonality  

 

where p(M ) = ∩

θ

∈P θ(m), q(M ) = ∩H∈qH(m). 

 

Definition 3. Two types  p, r 

∈  S(A) are almost  orthogonal (p⊥ar) if for any α¯ ∈ p(N ), ∀β  ∈ (N ) 

then we have α and β

¯ - A-definable and if p⊥aq one of them is stationary then p⊥ωq .  Two types p, 

r 

∈  S

1

(A) are  c a l le d   n o t   almost  orthogonal (p

⊥ar) if the formula divides and gets inside. 

Definition 4. The  type  p(x¯) 

∈  Sn(A),  where  A  ⊆  M  from  theory  T  is  called definable  if  for  any 

it’s  formula  φ(x¯, y¯)  there  exist  another  formula  ”controller” Hφ(x¯,y¯)(y¯, m

¯ ) 

∀a¯ ∈ A such that 

φ(x¯, a¯) 

∈ p ⇐⇒ M  |= Hφ,p(a¯, m

¯ ). 

434 

 

An n-type p(x¯) is called complete if it is maximal. It means, if for all formula φ(x¯) 

∈ M(A, x) either 

φ(x¯) 

∈ p(x¯) or ¬φ(x¯) ∈ p(x¯) is true. 

Note. If p(x) 

∈ S

1

(A) and q(y) 

∈ S

1

(A), then p(x) 

⊥ω  q(y) ⇔ p(x) ∪ q(y) is complete  2-type.   

Criterii for definability of 1-type in weakly o-minimal theories.  

Proposition 1: Let p, q 

∈  S

1

(A), p 

⊥ω  q. Then the following is valid: 

1.

 

If p is strictly definable then

⇐⇒ q is strictly definable. 

2.

 

If p is irrational then q is also irrational and vice versa. 

3.

 

If p is quasi-rational then 

⇐⇒ q is quasi-rational. 

4.

 

⊥ω  is the equivalence relation on S1(A). 

5.

 

Let p 

∈ S

1

(A) is quasi-rational. Then p is definable. 

6.

 

If p is quasi-rational or isolated then p is definable. 

7.

 

If A=M , where M is a model(structure on which theory is hold), then p is definable if and only 

if  p is quasi-rational. 

жүктеу/скачать 15,88 Mb.

Достарыңызбен бөлісу: