On free semilattice-ordered semigroups satisfying x n =x

Let B(k,0,n) denote the group with k generators which is free in the group variety defined by the identity x ⁿ =1. Let B _slo (k,1,n) denote the semilattice-ordered semigroup with k generators which is free in the semilattice-ordered semigroup variety defined by the identity x ⁿ =x. We prove a generalization of the Green-Rees theorem: B _slo (k,1,n) is finite for all k≥1 if and only if B(k,0,n−1) is finite for all k≥1. We find a formula for card(B _slo (1,1,n)). We construct B _slo (k,1,n) for some concrete values of k and n.     

The Hardness of 3-Uniform Hypergraph Coloring

We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n^1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c₂ > c₁ > 1, coloring a k-uniform c₁-colorable hypergraph with c₂ colors is NP-hard; the case k = 2, however, remains wide open. This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges. * Research supported by NSF grant CCR-9987845. † Supported by an Alon Fellowship and by NSF grant CCR-9987845. ‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery.     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs

The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 (2006)] have proved that Bn is edge-bipancyclic for n ≥ 5 and Bn-F is bipancyclic when n ≥ 4 and |F | ≤ n-3. In this paper, we improve this result by showing that for any edge set F of Bn with |F | ≤ n-3, every edge of Bn F lies on a cycle of every even length from 6 to n! for n ≥ 5 and every edge of Bn F lies on a cycle of every even length from 8 to n! for n = 4.     

Non-<Emphasis Type="Italic">φ</Emphasis>-admissible normal subgroups of free burnside groups

In the present paper for arbitrary automorphism φ of the free Bunside group B(m, n) and for any odd number n ≥ 1003 a sufficient condition for existence of non-φ-admissible normal subgroup of B(m, n) was found. In particular, if automorphism φ is normal, then for any basis {a ₁, a ₂, …, a _m } of the group B(m, n) there is an integer k such that for each i the elements a _i and φ(a i) ^k are conjugates.     

On the law of the iterated logarithm for permuted lacunary sequences

It is known that for any smooth periodic function f the sequence (f(2 ^k x)) _k≥1 behaves like a sequence of i.i.d. random variables; for example, it satisfies the central limit theorem and the law of the iterated logarithm. Recently Fukuyama showed that permuting (f(2 ^k x)) _k≥1 can ruin the validity of the law of the iterated logarithm, a very surprising result. In this paper we present an optimal condition on (n _k ) _k≥1, formulated in terms of the number of solutions of certain Diophantine equations, which ensures the validity of the law of the iterated logarithm for any permutation of the sequence (f(n _k x)) _k≥1. A similar result is proved for the discrepancy of the sequence ({n _k x}) _k≥1, where {·} denotes the fractional part.     

Depth of functions of the <Emphasis Type="Italic">k</Emphasis>-valued logic in infinite bases

The realization of functions of the k-valued logic by circuits is considered over an arbitrary infinite complete basis B. The Shannon function D _B (n) of the circuit depth over B is examined (for any positive integer n the value D _B (n) is the minimal depth sufficient to realize every function of the k-valued logic of n variables by a circuit over B). It is shown that for each fixed k ≥ 2 and for any infinite complete basis B either there exists a constant α ≥ 1 such that D _B (n) = α for all sufficiently large n, or there exist constants β (β > 0), γ, δ such that βlog₂ n ≤ D _B (n) ≤ γlog₂ n + δ for all n.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

Edge intersection graphs of systems of paths on a grid with a bounded number of bends

We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n²) is needed. We also show several results related to the classes B_k-EPG, where B_k-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph K_m,n does not belong to B_2m−3-EPG (it is known that this graph belongs to B_2m−2-EPG); for any odd integer k we have B_k-EPG B_k+1-EPG; there is no number k such that all graphs belong to B_k-EPG; only 2^O(knlog(kn)) out of all the labeled graphs with n vertices are in B_k-EPG.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.     

Existence result for minimal hypersurfaces¶with a prescribed finite number of planar ends

Paralleling what has been done for minimal surfaces in ℝ³, we develop a gluing procedure to produce, for any k≥ 2 and any n≥ 3 complete immersed minimal hypersurfaces of ℝ ^{n +1} which have k planar ends. These surfaces are of the topological type of a sphere with k punctures and they all have finite total curvature. Received: 1 July 1999 / Revised version: 31 May 2000     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

An acyclic extension of the braid group

We relate Artin's braid groupB _℞=lim_→B_n to a certain groupF′ ofpl-homeomorphisms of the interval. Namely, there exists a short exact sequence 1→B _∞→A→F′→1 whereH _kA=0,k≥1.     

Bonds Intersecting Cycles In A Graph

Let G be a k-connected graph G having circumference c ≥ 2k. It is shown that for k ≥ 2, then there is a bond B which intersects every cycle of length c-k + 2 or greater.     

Spanning k-Trees of n-Connected Graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg _G (u) + deg _G (v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.