一类新的部分差集以及分圆数的新性质

本文研究了分圆理论与部分差集,强正则图的关系.利用分圆方法,构造了一类新的部分差集,并反过来得到了分圆数的一些新性质.     

Shift graphs on precompact families of finite sets of natural numbers

We study graphs defined on families of finite sets of natural numbers and their chromatic properties. Of particular interest are graphs for which the edge relation is given by the shift. We show that when considering shift graphs with infinite chromatic number, one can center attention on graphs defined on precompact thin families. We define a quasi-order relation on the collection of uniform families defined in terms of homomorphisms between their corresponding shift graphs, and show that there are descending ${\omega }_1$-sequences. Specker graphs are also considered and their relation with shift graphs is established. We characterize the family of Specker graphs which contain a homomorphic image of a shift graph.     

Four-regular graphs with rigid vertices associated to DNA recombination

Genome rearrangement and homological recombination processes have been modeled by Angeleska et al. [A. Angeleska, N. Jonoska, M. Saito, DNA recombinations through assembly graphs, Discrete Appl. Math. 157 (2009) 3020–3037] as 4-regular spacial graphs with rigid vertices, called assembly graphs. These graphs can also be represented by double occurrence words called assembly words. The rearranged DNA segments are modeled by certain types of paths in the assembly graphs called polygonal paths. The minimum number of polygonal paths visiting all vertices in a graph is called an assembly number for the graph.In this paper, we give formulas for counting certain types of assembly graphs and assembly words. Some of these formulas produce sequences not previously reported at the Online Encyclopedia of Integer Sequences (http://oeis.org). We provide a sharp upper bound for the number of polygonal paths in Hamiltonian sets of polygonal paths, and present a family of graphs that achieves this bound. We investigate changes in the assembly numbers as a result of graph compositions. Finally, we introduce a polynomial invariant for assembly graphs and show properties of this invariant.     

Ramsey Numbers for Partially-Ordered Sets

We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.     

The graph formulation of the union-closed sets conjecture

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three.     

A Generalization of Kneser Graphs

Mathematical Notes - Graphs which are analogs of Kneser graphs are studied. The problem of determining the chromatic numbers of these graphs is considered. It is shown that their structure is...     

Efficient identification of independence networks using mutual information

Conditional independence graphs are now widely applied in science and industry to display interactions between large numbers of variables. However, the computational load of structure identification grows with the number of nodes in the network and the sample size. A tailored version of the PC algorithm is proposed which is based on mutual information tests with a specified testing order, combined with false negative reduction and false positive control. It is found to be competitive with current structure identification methodologies for both estimation accuracy and computational speed and outperforms these in large scale scenarios. The methodology is also shown to approximate dense networks. The comparisons are made on standard benchmarking data sets and an anonymized large scale real life example.     

Construction and Dimension Analysis for a Class of Fractal Functions

In this paper, we construct a class of nowhere differentiable continuous functions by means of the Cantor series expression of real numbers. The constructed functions include some known nondifferentiable functions, such as Bush type functions. These functions are fractal functions since their graphs are in general fractal sets. Under certain conditions, we investigate the fractal dimensions of the graphs of these functions, compute the precise values of Box and Packing dimensions, and evaluate the Hausdorff dimension. Meanwhile, the Holder continuity of such functions is also discussed.     

Maximal independent sets in graphs with at most r cycles

We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with n vertices and at most r cycles. The second family is all graphs of the first family which are connected and satisfy n ≥ 3r. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 270–282, 2006     

Intersection Theorems for Infinite Families of Convex Sets in Graphs

We prove several Helly-type theorems for infinite families of geodesically convex sets in infinite graphs. That is, we determine the least cardinal n such that any family of (particular) convex sets in some infinite graph has a nonempty intersection whenever each of its subfamilies of cardinality less than n has a nonempty intersection. We obtain some general compactness theorems, and some particular results for pseudo-modular graphs, strongly dismantlable graphs and ball-Helly graphs.     

A Family of Antipodal Distance-Regular Graphs Related to the Classical Preparata Codes

A new family of distance-regular graphs is constructed. They are antipodal 2^2t–1-fold covers of the complete graph on 2^2t vertices. The automorphism groups are determined, and the extended Preparata codes are reconstructed using walks on these graphs.There are connections to other interesting structures: the graphs are equivalent to certain generalized Hadamard matrices; and their underlying 3-class association scheme is formally dual to the scheme of a system of linked symmetric designs obtained from Kerdock sets of skew matrices in characteristic two.     

Dimensions of the coordinate functions of space-filling curves

The graphs of coordinate functions of space-filling curves such as those described by Peano, Hilbert, Pólya and others, are typical examples of self-affine sets, and their Hausdorff dimensions have been the subject of several articles in the mathematical literature. In the first half of this paper, we describe how the study of dimensions of self-affine sets was motivated, at least in part, by these coordinate functions and their natural generalizations, and review the relevant literature. In the second part, we present new results on the coordinate functions of Pólya's one-parameter family of space-filling curves. We give a lower bound for the Hausdorff dimension of their graphs which is fairly close to the box-counting dimension. Our techniques are largely probabilistic. The fact that the exact dimension remains elusive seems to indicate the need for further work in the area of self-affine sets.     

Graph Products,Fourier Analysis and Spectral Techniques

We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others, complete graphs, line graphs of regular graphs which contain a perfect matching and Kneser graphs. In many cases this also characterizes the optimal colorings of these products.We show that the independent sets induced by the base graph are the only maximum-size independent sets. Furthermore we give a qualitative stability statement: any independent set of size close to the maximum is close to some independent set of maximum size.Our approach is based on Fourier analysis on Abelian groups and on Spectral Techniques. To this end we develop some basic lemmas regarding the Fourier transform of functions on generalizing some useful results from the case.     

On domination numbers of Cartesian product of paths

We show the link between the existence of perfect Lee codes and minimum dominating sets of Cartesian products of paths and cycles. From the existence of such a code we deduce the asymptotical values of the domination numbers of these graphs.     

Intrinsic Lipschitz Graphs Within Carnot Groups

A Carnot group is a connected, simply connected, nilpotent Lie group with stratified Lie algebra. We study the notions of intrinsic graphs and of intrinsic Lipschitz graphs within Carnot groups. Intrinsic Lipschitz graphs are the natural local analogue inside Carnot groups of Lipschitz submanifolds in Euclidean spaces, where “natural” emphasizes that the notion depends only on the structure of the algebra. Intrinsic Lipschitz graphs unify different alternative approaches through Lipschitz parameterizations or level sets. We provide both geometric and analytic characterizations and a clarifying relation between these graphs and Rumin’s complex of differential forms.     

Girth of pancake graphs

We consider four families of pancake graphs, which are Cayley graphs, whose vertex sets are either the symmetric group on n objects or the hyperoctahedral group on n objects and whose generating sets are either all reversals or all reversals inverting the first k elements (called prefix reversals). We find that the girth of each family of pancake graphs remains constant after some small threshold value of n.     

Random sets. A survey of results and applications

A survey of current directions in the theory of random closed sets is presented; these include: the central limit theorem, the law of large numbers for Minkowski sums and unions of random sets, semi-Markov random closed sets, Boolean models and statistical estimation of their parameters, specification of distributions and associated problems of capacity theory. Weak convergence of random closed sets is defined and its application to limit theorems for graphs and epi-graphs of random processes and problems of stochastic optimization is described. Other connections with the theory of random processes (level sets, multivalued and controllable random processes) are also discussed.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 12, pp. 1587–1599, December, 1991.     

Distance-regular Cayley graphs with least eigenvalue $$$$

We classify the distance-regular Cayley graphs with least eigenvalue \(-2\) and diameter at most three. Besides sporadic examples, these comprise of the lattice graphs, certain triangular graphs, and line graphs of incidence graphs of certain projective planes. In addition, we classify the possible connection sets for the lattice graphs and obtain some results on the structure of distance-regular Cayley line graphs of incidence graphs of generalized polygons.     

Algorithmic aspects of intersection graphs and representation hypergraphs

Let be a family of sets. The intersection graph of is obtained by representing each set in by a vertex and connecting two vertices by an edge if and only if their corresponding sets intersect. Of primary interest are those classes of intersection graphs of families of sets having some specific topological or other structure. The grandfather of all intersection graphs is the class of interval graphs, that is, the intersection graphs of intervals on a line.The scope of research that has been going on in this general area extends from the mathematical and algorithmic properties of intersection graphs, to their generalizations and graph parameters motivated by them. In addition, many real-world applications involve the solution of problems on such graphs.In this paper a number of topics in algorithmic combinatorics which involve intersection graphs and their representative families of sets are presented. Recent applications to computer science are also discussed. The intention of this presentation is to provide an understanding of the main research directions which have been investigated and to suggest possible new directions of research.     

A class of threshold and domishold graphs: equistable and equidominating graphs

A threshold graph (respectively domishold graph) is a graph for which the independent sets (respectively the dominating sets) can be characterized by the 0, 1-solutions of a linear Inequality (see [1] and [3]).We define here the graphs for which the maximal independent sets (respectively the minimal dominating sets) are characterized by the 0, 1-solutions of a linear equation. Such graphs are said to be equistable (respectively equldominating).We characterize (by their architectural structure and by forbidden induced subgraphs) threshold graphs and domishold graphs which are equistable or equidominating.A larger class of equistable graphs is also presented.