CiteSeerX Scientific Literature Digital Library and Search Engine
(2,288,305 recursos)
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge

Mostrando recursos 1 - 20 de 2,223,523

1.
Counting and sampling H-colourings - Martin Dyer; Leslie Ann Goldberg; Mark Jerrum
For counting problems in #P which are “essentially self-reducible”, it is known that sampling and approximate counting are equivalent. However, many problems of interest do not have such a structure and there is already some evidence that this equivalence does not hold for the whole of #P. An intriguing example is the class of H-colouring problems, which have recently been the subject of much study, and their natural generalisation to vertex- and edge-weighted versions. Particular cases of the counting-to-sampling reduction have been observed, but it has been an open question as to how far these reductions might extend to any...

2.
Fractional Kernels in Digraphs - Ron Aharoni; Ron Holzman
We define a fractional version of the notion of "kernels" in digraphs and prove that every clique acyclic digraph (i.e., one in which no clique contains a cycle) has a fractional kernel. Using this we give a short proof of a recent result of Boros and Gurvich (proving a conjecture of Berge and Duchet) that every clique acyclic orientation of a perfect graph has a kernel.

3.
DISCRETE POLYMATROIDS - Marius Vlădoiu
In this article we give a survey on some recent developments about discrete polymatroids.

4.
A characterization of balanced episturmian sequences - Geneviève Paquin; Laurent Vuillon
It is well-known that Sturmian sequences are the non ultimately periodic sequences that are balanced over a 2-letter alphabet. They are also characterized by their complexity: they have exactly (n + 1) distinct factors of length n. A natural generalization of Sturmian sequences is the set of infinite episturmian sequences. These sequences are not necessarily balanced over a k-letter alphabet, nor are they necessarily aperiodic. In this paper, we characterize balanced episturmian sequences, periodic or not, and prove Fraenkel’s conjecture for the special case of episturmian sequences. It appears that balanced episturmian sequences are all ultimately periodic and they can...

5.
Ramsey Properties of Families of Graphs - Ronald Graham; Tomasz Łuczak; Vojtech Rödl; Andrzej Rucinski
For a graph F and natural numbers a1;...; ar; let F!ða1;...; arÞ denote the property that for each coloring of the edges of F with r colors, there exists i such that some copy of the complete graph Kai is colored with the ith color. Furthermore, we write ða1;...; arÞ!ðb1;...; bsÞ if for every F for which F!ða1;...; arÞ we have also F!ðb1;...; bsÞ: In this note, we show that a trivial sufficient condition for the relation ða1;...; arÞ!ðb1;...; bsÞ is necessary as well.

6.
On the largest eigenvalue of non-regular graphs - Bolian Liu; Jian Shen; Xinmao Wang
We study the spectral radius of connected non-regular graphs. Let λ1(n, Δ) be the maximum spectral radius among all connected non-regular graphs with n vertices and maximum degree Δ. We prove that Δ − λ1(n, Δ) = Θ(Δ/n2). This improves two recent results by Stevanović and Zhang, respectively.

7.
Polynomial-time counting and sampling of two-rowed contingency tables - Martin Dyer; Catherine Greenhill
In this paper a Markov chain for contingency tables with two rows is defined. The chain is shown to be rapidly mixing using the path coupling method. We prove an upper bound for the mixing time of the chain. The upper bound is quadratic in the number of columns and linear in the logarithm of the table sum. By considering a specific problem, we prove a lower bound for the mixing time of the chain. The lower bound is quadratic in the number of columns and linear in the logarithm of the number of columns. A fully polynomial randomised approximation...

8.
The Bergman complex of a matroid and phylogenetic trees - Federico Ardila; Caroline J. Klivans
We study the Bergman complex B(M) of a matroid M: a polyhedral complex which arises in algebraic geometry, but which we de-scribe purely combinatorially. We prove that a natural subdivision of the Bergman complex of M is a geometric realization of the order complex of its lattice of flats. In addition, we show that the Bergman fan � B(Kn) of the graphical matroid of the complete graph Kn is homeomorphic to the space of phylogenetic trees Tn.

9.
I-graphs and the corresponding configurations - Marko Boben; Tomaz Pisanski; Arjana Zitnik
We consider the class of I-graphs I(n, j, k), which is a generalization over the class of the generalized Petersen graphs. We study different properties of I-graphs such as connectedness, girth and whether they are bipartite or vertex-transitive. We give an efficient test for isomorphism of I-graphs and characterize the automorphism groups of I-graphs. Regular bipartite graphs with girth at least 6 can be considered as Levi graphs of some symmetric combinatorial configurations. We consider configurations which arise from bipartite I-graphs. Some of them can be realized in the plane as cyclic astral configurations, i.e. as geometric configurations with maximal...

10.
Using DPLL for efficient OBDD construction - Jinbo Huang; Adnan Darwiche
The DPLL procedure has found great success in SAT, where search terminates on the first solution discovered. We show that this procedure is equally promising in a problem where exhaustive search is used, given that it is augmented with appropriate caching. Specifically, we propose two DPLL-based algorithms that construct OBDDs for CNF formulas. These algorithms have a worst-case complexity that is linear in the number of variables and size of the CNF, and exponential only in the cutwidth or pathwidth of the variable ordering. We show how modern SAT techniques can be harnessed by implementing the algorithms on top of...

12.
Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6 - Edita Máčajová; Martin Skoviera
A graph is hypohamiltonian if it is not hamiltonian but every vertex-deleted subgraph is. In this paper we study hypohamiltonian snarks – cubic hypohamiltonian graphs with chromatic index 4. We describe a method, based on superposition of snarks, which produces new hypohamiltonian snarks from old ones. By choosing suitable ingredients we can achieve that the resulting graphs are cyclically 5connected or 6-connected. Previously, only three sporadic hypohamiltonian snarks with cyclic connectivity 5 had been found, while the flower snarks of Isaacs were the only known family of cyclically 6-connected hypohamiltonian snarks. Our method produces hypohamiltonian snarks with cyclic connectivity 5...

13.
A note on three types of quasisymmetric functions - T. Kyle Petersen
In the context of generating functions for P-partitions, we revisit three flavors of quasisymmetric functions: Gessel’s quasisymmetric functions, Chow’s type B quasisymmetric functions, and Poirier’s signed quasisymmetric functions. In each case we use the inner coproduct to give a combinatorial description (counting pairs of permutations) to the multiplication in: Solomon’s type A descent algebra, Solomon’s type B descent algebra, and the Mantaci-Reutenauer algebra, respectively. The presentation is brief and elementary, our main results coming as consequences of P-partition theorems already in the literature.

14.
LINEAR QUANTUM ADDITION RULES - Melvyn B. Nathanson
The quantum integer [n]q is the polynomial 1 + q + q 2 + · · · + q n−1. Two sequences of polynomials U = {un(q)} ∞ n=1 and V = {vn(q)} ∞ n=1 define a linear addition rule ⊕ on a sequence F = {fn(q)} ∞ n=1 by fm(q) ⊕ fn(q) = un(q)fm(q) + vm(q)fn(q). This is called a quantum addition rule if [m]q ⊕ [n]q = [m + n]q for all positive integers m and n. In this paper all linear quantum addition rules are determined, and all solutions of the corresponding functional equations fm(q) ⊕ fn(q)...

15.
THE TRIBONACCI SUBSTITUTION - S. W. Rosema; R. Tijdeman
We study the discretised segments generated by the iterated Tribonacci substitution and the projections of the integer points on them to some plane. After suitable transformations we get a sequence of finite two-dimensional words which tends to a doubly rotational word on Z 2. (Without scaling we would get the Rauzy fractal.) As an introduction we start with the corresponding case of the Fibonacci substitution.

19.
Can a Graph Have Distinct Regular Partitions? - Noga Alon; Asaf Shapira; Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph have two “distinct” regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very “similar”. En route,...