BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Which permutations of a probability distribution on integers minimize variance? Let X be a random variable on a set of integers {x1,…,xN} such that P(Xi=xi)=pi, i∈{1,…,N}. Let (p(1),…,p(N)) be the sequence (p1,…,pN) ordered non-increasingly. Let X+ be the random variable defined by P(X+=0)=p(1), P(X+=1)=p(2), P(X+=−1)=p(3),…,P(X+=(−1)N⌊2N⌋)=p(N). In this short note we generalize and prove the inequality VarX+≤VarX.
The paper [J. Balogh, B. Bollobás, D. Weinreich, A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005) 29--48] identifies a jump in the speed of hereditary graph properties to the Bell number Bn and provides a partial characterisation of the family of minimal classes whose speed is at least Bn. In the present paper, we give a complete characterisation of this family. Since this family is infinite, the decidability of the problem of determining if the speed of a hereditary property is above or below the Bell number is questionable. We answer this question positively by showing that there exists an algorithm which, given a finite set F of graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the set F is above or below the Bell number. For properties defined by infinitely many minimal forbidden induced subgraphs, the speed is known to be above the Bell number.
A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore admits a characterization in terms of minimal forbidden induced subgraphs. In spite of quite active study of unit disk graphs very little is known about minimal forbidden induced subgraphs for this class. We found only finitely many minimal non unit disk graphs in the literature. In this paper we study in a systematic way forbidden induced subgraphs for the class of unit disk graphs. We develop several structural and geometrical tools, and use them to reveal infinitely many new minimal non unit disk graphs. Further we use these results to investigate structure of co-bipartite unit disk graphs. In particular, we give structural characterization of those co-bipartite unit disk graphs whose edges between parts form a C4-free bipartite graph, and show that bipartite complements of these graphs are also unit disk graphs. Our results lead us to propose a conjecture that the class of co-bipartite unit disk graphs is closed under bipartite complementation.
We consider the problem Scattered Cycles which, given a graph G and two positive integers r and ℓ, asks whether G contains a collection of r cycles that are pairwise at distance at least ℓ. This problem generalizes the problem Disjoint Cycles which corresponds to the case ℓ=1. We prove that when parameterized by r, ℓ, and the maximum degree Δ, the problem Scattered Cycles admits a kernel on 24ℓ2Δℓrlog(8ℓ2Δℓr) vertices. We also provide a (16ℓ2Δℓ)-kernel for the case r=2 and a (148Δrlogr)-kernel for the case ℓ=1. Our proofs rely on two simple reduction rules and a careful analysis.
Recently, Daligault, Rao and Thomassé asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two reasons why this questions is interesting. First, it connects two seemingly unrelated notions. Second, if the question is answered affirmatively, this will have a strong algorithmic consequence. In particular, this will mean (through the use of Courcelle theorem [2]), that any problem definable in Monadic Second Order Logic can be solved in a polynomial time on any class well-quasi-ordered by the induced subgraph relation. In the present paper, we answer this question affirmatively for graphs without large bicliques. Thus the above algorithmic consequence is true, for example, for classes of graphs of bounded degree.
We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting P5 and a clique of any size is well-quasi-ordered. This is proved by giving a structural decomposition of the corresponding permutations. We also exhibit three infinite antichains to show that the classes of permutation graphs omitting {P6,K6}, {P7,K5}, and {P8,K4} are not well-quasi-ordered.
The idea of implicit representation of graphs was introduced in [S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Mathematics, 5 (1992) 596--603] and can be defined as follows. A representation of an n-vertex graph G is said to be implicit if it assigns to each vertex of G a binary code of length O(logn) so that the adjacency of two vertices is a function of their codes. Since an implicit representation of an n-vertex graph uses O(nlogn) bits, any class of graphs admitting such a representation contains 2O(nlogn) labelled graphs with n vertices. In the terminology of [J. Balogh, B. Bollobás, D. Weinreich, The speed of hereditary properties of graphs, J. Combin. Theory B 79 (2000) 131--156] such classes have at most factorial speed of growth. In this terminology, the implicit graph conjecture can be stated as follows: every class with at most factorial speed of growth which is hereditary admits an implicit representation. The question of deciding whether a given hereditary class has at most factorial speed of growth is far from being trivial. In the present paper, we introduce a number of tools simplifying this question. Some of them can be used to obtain a stronger conclusion on the existence of an implicit representation. We apply our tools to reveal new hereditary classes with the factorial speed of growth. For many of them we show the existence of an implicit representation.
Let X be a family of graphs and Xn the set of n-vertex graphs in X. A graph U(n) containing all graphs from Xn as induced subgraphs is called n-universal for X. Moreover, we say that U(n) is a proper n-universal graph for X if it belongs to X. In the present paper, we construct a proper n-universal graph for the class of split permutation graphs. Our solution includes two ingredients: a proper universal 321-avoiding permutation and a bijection between 321-avoiding permutations and symmetric split permutation graphs. The n-universal split permutation graph constructed in this paper has 4n3 vertices, which means that this construction is order-optimal.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.