Balanced partitions of two sets of points in the plane

We prove the following theorem. Let m≥2 and q≥1 be integers and let S and T be two disjoint sets of points in the plane such that no three points of ST are on the same line, |S|=2q and |T|=mq. Then ST can be partitioned into q disjoint subsets P₁,P₂,…,P_q satisfying the following two conditions: (i) conv(P_i)∩conv(P_j)=φ for all 1≤i<j≤q, where conv(P_i) denotes the convex hull of P_i; and (ii) |P_i∩S|=2 and |P_i∩T|=m for all 1≤i≤q.     

On strong 1-factors and Hamilton weights of cubic graphs

A 1-factor M of a cubic graph G is strong if |M∩T|=1 for each 3-edge-cut T of G. It is proved in this paper that a cubic graph G has precisely three strong 1-factors if and only if the graph can be obtained from K₄ via a series of ↔Y operations. Consequently, the graph G admits a Hamilton weight and is uniquely edge-3-colorable.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

On-line algorithms for ordered sets and comparability graphs

We discuss several results concerning on-line algorithms for ordered sets and comparability graphs. The main new result is on the problem of on-line transitive orientation. We view on-line transitive orientation of a comparability graph G as a two-person game. In the ith round of play, 1 i | V(G)|, player A names a graph G_i such that G_i is isomorphic to a subgraph of G, |V(G_i)| = i, and G_i−1 is an induced subgraph of G_i if i> 1. Player B must respond with a transitive orientation of G_i which extends the transitive orientation given to G_i−1 in the previous round of play. Player A wins if and only if player B fails to give a transitive orientation to G_i for some i, 1 i |V(G)|. Our main result shows that player A has at most three winning moves. We also discuss applications to on-line clique covering of comparability graphs, and we mention some open problems.     

A characterization on n-critical economical generalized tic-tac-toe games

There is a so called generalized tic-tac-toe game playing on a finite set X with winning sets A₁, A₂,…, A_m. Two players, F and S, take in turn a previous untaken vertex of X, with F going first. The one who takes all the vertices of some winning set first wins the game. Erd s and Selfridge proved that if |A₁|=|A₂|==|A_m|=n and m<2ⁿ⁻¹, then the game is a draw. This result is best possible in the sense that once m=2ⁿ⁻¹, then there is a family A₁, A₂,…, A_m so that F can win. In this paper we characterize all those sets A₁,…, A_2n−1 so that F can win in exactly n moves. We also get similar result in the biased games.     

Ramsey linear families and generalized subdivided graphs

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V₁, V₂,…, V_a such that for each i at most d vertices in V₁ … V_i have neighbors in V_i+1 and r(K_k, V_i) p | V(G) |, where V_i denotes the subgraph of G induced by V_i. Then there exists a number c depending only on p, d, and k such that r(K_k, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

Sperner''s theorem with constraints

A set X of subsets of an n-element set S is called an anti-chain if no two elements of X are related by set-wise inclusion. Sperner showed [8] that max |X|=(ⁿ_[n/2]), where |X| denotes the number of elements in X and the maximum is taken over all anti-chains of subsets of S.

Let non-negative integers i_o<n and m_io≠0, m_io+1,…m_n be given. In this paper we give an algorithm for calculating max |X| where the maximum is taken only over anti-chains containing exactly m_i i-element subsets of S for i_o i n.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

On ramsey numbers for large disjoint unions of graphs

Let be a fixed finite set of connected graphs. Results are given which, in principle, permit the Ramsey number r(G, H) to be evaluated exactly when G and H are sufficiently large disjoint unions of graphs taken from . Such evaluations are often possible in practice, as shown by several examples. For instance, when m and n are large, and mn,

r(mK_k, nK_l)=(k − 1)m+ln+r(K_k−1, K_l−1)−2.

     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

Almost perfect matchings in random uniform hypergraphs

We consider the following model H_r(n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = (r − 1)n. Each r-subset of V × (_r−1^U) is chosen to be an edge of H ε H_r(n, p) with probability p = p(n), all choices being independent. It is shown that for every 0 < < 1 if P = (C ln n)/n^r−1 with C = C() sufficiently large, then almost surely every subset V₁ V of size | V₁ | = (1 − )n is matchable, that is, there exists a matching M in H such that every vertex of V₁ is contained in some edge of M.     

The coordinate representation of a graph and n-universal graph of radius 1

Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space Eⁿ. Cube vertices have integer coordinates. The coordinate matrix, A(G)={v_nk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements v_nk≠v_pk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3ⁿ⁻² vertices that contains as an induced subgraph a copy of any graph on n vertices.     

Nonchordal positive semidefinite stochastic matrices

Let K_nbe the convex set of n×npositive semidefinite doubly stochastic matrices. If Aε k_n, the graph of A,G(A), is the graph on n vertices with (i,j) an edge if a_ij ≠ 0i≠ j. We are concerned with the extreme points in K_n. In many cases, the rank of Aand G(A) are enough to determine whether A is extreme in K_n. This is true, in particular, if G(A)is a special kind of nonchordal graph, i.e., if no two cycles in G(A)have a common edge.     

On index of total boundedness of (strictly) o-bounded groups

Let G be a metrizable topological group. Denote by itb(G) the smallest cardinality of a cover of G by totally bounded subsets of G. A group G is defined to be σ-bounded if itb(G)₀. The group G is called o-bounded if for every sequence (U_n)_nω of neighborhoods of the identity in G there exists a sequence (F_n)_nω of finite subsets in G such that G=_nωF_n·U_n; G is called strictly o-bounded (respectively OF-determined) if the second player (respectively one of the players) has a winning strategy in the following game OF: two players, I and II, choose at every step n an open neighborhood U_n of the identity in G and a finite subset F_n of G, respectively. The player II wins if G=_nωF_n·U_n.

For a second countable group G the following results are proven. . If G is strictly o-bounded, then itb(G)₁ and G is σ-bounded or meager. If the space G is analytic, then the group is OF-determined and satisfies . G is σ-bounded if it is strictly o-bounded and one of the following conditions holds: (i) G is analytic; (ii) ; (iii) (MA+¬CH) holds; (iv) analytic games are determined; (v) there exists a measurable cardinal. Also we show that under (MA) every non-locally compact Polish Abelian divisible group contains a Baire o-bounded OF-undetermined subgroup.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.