for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 2007 journals)     - ANIMATION AND SIMULATION (30 journals)    - ARTIFICIAL INTELLIGENCE (98 journals)    - AUTOMATION AND ROBOTICS (98 journals)    - CLOUD COMPUTING AND NETWORKS (60 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (9 journals)    - COMPUTER GAMES (16 journals)    - COMPUTER PROGRAMMING (24 journals)    - COMPUTER SCIENCE (1169 journals)    - COMPUTER SECURITY (46 journals)    - DATA BASE MANAGEMENT (13 journals)    - DATA MINING (32 journals)    - E-BUSINESS (22 journals)    - E-LEARNING (29 journals)    - ELECTRONIC DATA PROCESSING (21 journals)    - IMAGE AND VIDEO PROCESSING (39 journals)    - INFORMATION SYSTEMS (108 journals)    - INTERNET (92 journals)    - SOCIAL WEB (50 journals)    - SOFTWARE (34 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1169 journals)                  1 2 3 4 5 6 | Last
 COMBINATORICA   [SJR: 1.296]   [H-I: 38]   [0 followers]  Follow         Hybrid journal (It can contain Open Access articles)    ISSN (Print) 1439-6912 - ISSN (Online) 0209-9683    Published by Springer-Verlag  [2355 journals]
• Cocliques in the Kneser graph on line-plane flags in PG(4; q )
• Authors: Aart Blokhuis; Andries E. Brouwer
Pages: 795 - 804
Abstract: Abstract We determine the independence number of the Kneser graph on line-plane flags in the projective space PG(4;q). We also classify the corresponding maximum-size cocliques.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3438-2
Issue No: Vol. 37, No. 5 (2017)

• The distribution of factorization patterns on linear families of
polynomials over a finite field
• Authors: Eda Cesaratto; Guillermo Matera; Mariana Pérez
Pages: 805 - 836
Abstract: Abstract We estimate the number A λ of elements on a linear family A of monic polynomials of F q [T] of degree n having factorization pattern $$\lambda : = {1^{{\lambda _1}}}{2^{{\lambda _2}}} \cdot \cdot \cdot {n^{{\lambda _n}}}$$ . We show that A λ = T(λ)q n-m + O(q n-m-1/2), where T(λ) is the proportion of elements of the symmetric group of n elements with cycle pattern λ and m is the codimension of A. Furthermore, if the family A under consideration is “sparse”, then A λ =T(λ)q n-m +O(q n-m-1). Our estimates hold for fields F q of characteristic greater than 2. We provide explicit upper bounds for the constants underlying the O-notation in terms of λ and A with “good” behavior. Our approach reduces the question to estimate the number of F q -rational points of certain families of complete intersections defined over F q . Such complete intersections are defined by polynomials which are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning their singular locus, from which precise estimates on their number of F q -rational points are established.
PubDate: 2017-10-01
DOI: 10.1007/s00493-015-3330-5
Issue No: Vol. 37, No. 5 (2017)

• The fractional chromatic number of the plane
• Authors: Daniel W. Cranston; Landon Rabern
Pages: 837 - 861
Abstract: Abstract The chromatic number of the plane is the chromatic number of the uncountably infinite graph that has as its vertices the points of the plane and has an edge between two points if their distance is 1. This chromatic number is denoted χ(ℝ2). The problem was introduced in 1950, and shortly thereafter it was proved that 4≤χ(ℝ2)χ≤7. These bounds are both easy to prove, but after more than 60 years they are still the best known. In this paper, we investigate χ f (ℝ2), the fractional chromatic number of the plane. The previous best bounds (rounded to five decimal places) were 3.5556≤χ f (ℝ2)≤4.3599. Here we improve the lower bound to 76/21≈3.6190.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3380-3
Issue No: Vol. 37, No. 5 (2017)

• Density of 5/2-critical graphs
• Authors: Zdeněk Dvořák; Luke Postle
Pages: 863 - 886
Abstract: Abstract A graph G is 5/2-critical if G has no circular 5/2-coloring (or equivalently, homomorphism to C 5), but every proper subgraph of G has one. We prove that every 5/2-critical graph on n ≥ 4 vertices has at least $$\frac{{5n - 2}}{4}$$ edges, and list all 5/2-critical graphs achieving this bound. This implies that every planar or projective-planar graph of girth at least 10 is 5/2-colorable.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3356-3
Issue No: Vol. 37, No. 5 (2017)

• The Voronoi functional is maximized by the Delaunay triangulation in the
plane
• Authors: Herbert Edelsbrunner; Alexey Glazyrin; Oleg R. Musin; Anton Nikitenko
Pages: 887 - 910
Abstract: Abstract We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3308-y
Issue No: Vol. 37, No. 5 (2017)

• A tight lower bound for Szemerédi’s regularity lemma
• Authors: Jacob Fox; László Miklós Lovász
Pages: 911 - 951
Abstract: Abstract We determine the order of the tower height for the partition size in a version of Szemerédi’s regularity lemma. This addresses a question of Gowers.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3274-4
Issue No: Vol. 37, No. 5 (2017)

• On the chromatic number of a simplicial complex
• Authors: Konstantin Golubev
Pages: 953 - 964
Abstract: Abstract In [3] A. J. Hoffman proved a lower bound on the chromatic number of a graph in the terms of the largest and the smallest eigenvalues of its adjacency matrix. In this paper, we prove a higher dimensional version of this result and give a lower bound on the chromatic number of a pure d-dimensional simplicial complex in the terms of the spectra of the higher Laplacian operators.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3137-z
Issue No: Vol. 37, No. 5 (2017)

• The parameterised complexity of counting even and odd induced subgraphs
• Authors: Mark Jerrum; Kitty Meeks
Pages: 965 - 990
Abstract: Abstract We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting the k-vertex induced subgraphs having an odd number of edges. We demonstrate that both problems are #W[1]-hard when parameterised by k, in fact proving a somewhat stronger result about counting subgraphs with a property that only holds for some subset of k-vertex subgraphs which have an even (respectively odd) number of edges. On the other hand, we show that each of the problems admits an FPTRAS. These approximation schemes are based on a surprising structural result, which exploits ideas from Ramsey theory.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3338-5
Issue No: Vol. 37, No. 5 (2017)

• The multiplication table problem for bipartite graphs
• Authors: Bhargav P. Narayanan; Julian Sahasrabudhe; István Tomon
Pages: 991 - 1010
Abstract: Abstract We investigate the following generalisation of the ‘multiplication table problem’ of Erdős: given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs' Erdős’s problem of estimating the number of distinct products ab with a,b ≤ n is precisely the problem under consideration when the graph in question is the complete bipartite graph K n,n . In this note, we prove that the set of sizes of the induced subgraphs of any bipartite graph with m edges contains Ω(m/(logm)12) distinct elements.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3322-0
Issue No: Vol. 37, No. 5 (2017)

• Chromatic numbers of algebraic hypergraphs
• Authors: James H. Schmerl
Pages: 1011 - 1026
Abstract: Abstract Given a polynomial p(x 0,x 1,...,x k−1) over the reals ℝ, where each x i is an n-tuple of variables, we form its zero k-hypergraph H=(ℝ n , E), where the set E of edges consists of all k-element sets {a 0,a 1,...,a k−1}⊆ℝ n such that p(a 0,a 1,...,a k−1)=0. Such hypergraphs are precisely the algebraic hypergraphs. We say (as in [13]) that p(x 0,x 1,...,x k−1) is avoidable if the chromatic number χ(H) of its zero hypergraph H is countable, and it is κ-avoidable if χ(H≤κ. Avoidable polynomials were completely characterized in [13]. For any infinite κ, we characterize the κ-avoidable algebraic hypergraphs. Other results about algebraic hypergraphs and their chromatic numbers are also proved.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3393-y
Issue No: Vol. 37, No. 5 (2017)

• Nash-Williams’ cycle-decomposition theorem
• Authors: Carsten Thomassen
Pages: 1027 - 1037
Abstract: Abstract We give an elementary proof of the theorem of Nash-Williams that a graph has an edge-decomposition into cycles if and only if it does not contain an odd cut. We also prove that every bridgeless graph has a collection of cycles covering each edge at least once and at most 7 times. The two results are equivalent in the sense that each can be derived from the other.
PubDate: 2017-10-01
DOI: 10.1007/s00493-016-3424-8
Issue No: Vol. 37, No. 5 (2017)

• Strong inapproximability results on balanced rainbow-colorable hypergraphs
• Authors: Venkatesan Guruswami; Euiwoong Lee
Abstract: Abstract Consider a K-uniform hypergraph H = (V, E). A coloring c: V → {1, 2, …, k} with k colors is rainbow if every hyperedge e contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A simple polynomial-time algorithmnds a 2-coloring if H admits a perfectly balanced rainbow k-coloring. For a hypergraph that admits an almost balanced rainbow coloring, we prove that it is NP-hard to find an independent set of size ϵ, for any ϵ > 0. Consequently, we cannot weakly color (avoiding monochromatic hyperedges) it with O(1) colors. With k=2, it implies strong hardness for discrepancy minimization of systems of bounded set-size. One of our main technical tools is based on reverse hypercontractivity. Roughly, it says the noise operator increases q-norm of a function when q < 1, which is enough for some special cases of our results. To prove the full results, we generalize the reverse hypercontractivity to more general operators, which might be of independent interest. Together with the generalized reverse hypercontractivity and recent developments in inapproximability based on invariance principles for correlated spaces, we give a recipe for converting a promising test distribution and a suitable choice of an outer PCP to hardness of nding an independent set in the presence of highly-structured colorings. We use this recipe to prove additional results almost in a black-box manner, including: (1) the rst analytic proof of (K − 1 − ϵ)-hardness of K-Hypergraph Vertex Cover with more structure in completeness, and (2) hardness of (2Q+1)-SAT when the input clause is promised to have an assignment where every clause has at least Q true literals.
PubDate: 2017-12-14
DOI: 10.1007/s00493-016-3383-0

• Extending factorizations of complete uniform hypergraphs
• Authors: M. A. Bahmanian; Mike Newman
Abstract: Abstract We consider when a given r-factorization of the complete uniform hypergraph on m vertices K m h can be extended to an s-factorization of K n h . The case of r = s = 1 was first posed by Cameron in terms of parallelisms, and solved by Häggkvist and Hellgren. We extend these results, which themselves can be seen as extensions of Baranyai's Theorem. For r=s, we show that the “obvious” necessary conditions, together with the condition that gcd(m,n,h)=gcd(n,h) are sufficient. In particular this gives necessary and sufficient conditions for the case where r=s and h is prime. For r<s we show that the obvious necessary conditions, augmented by gcd(m,n,h)=gcd(n,h), n≥2m, and $$1 \leqslant \frac{s}{r} \leqslant \frac{m}{k}\left[ {1 - \left( {\begin{array}{*{20}{c}} {m - k} \\ h \end{array}} \right)/\left( {\begin{array}{*{20}{c}} m \\ h \end{array}} \right)} \right]$$ are sufficient, where k=gcd(m,n,h). We conclude with a discussion of further necessary conditions and some open problems.
PubDate: 2017-12-09
DOI: 10.1007/s00493-017-3396-3

• Finding perfect matchings in bipartite hypergraphs
• Authors: Chidambaram Annamalai
Abstract: Abstract Haxell’s condition [14] is a natural hypergraph analog of Hall’s condition, which is a wellknown necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell’s condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell’s condition is satisfied. We prove the existence of an efficient algorithm to find perfect matchings in bipartite hypergraphs whenever a stronger version of Haxell’s condition holds. Our algorithm can be seen as a generalization of the classical Hungarian algorithm for finding perfect matchings in bipartite graphs. The techniques we use to achieve this result could be of use more generally in other combinatorial problems on hypergraphs where disjointness structure is crucial, e.g., Set Packing.
PubDate: 2017-12-09
DOI: 10.1007/s00493-017-3567-2

• Multiplicative bases and an Erdős problem
• Authors: Péter Pál Pach; Csaba Sándor
Abstract: Abstract In this paper we investigate how small the density of a multiplicative basis of order h can be in {1,2,...,n} and in ℤ+. Furthermore, a related problem of Erdős is also studied: How dense can a set of integers be, if none of them divides the product of h others'
PubDate: 2017-12-09
DOI: 10.1007/s00493-016-3588-2

• On the linear span of lattice points in a parallelepiped
• Authors: Marcel Celaya
Abstract: Abstract Let Λ⊂R n be a lattice which contains the integer lattice Z n . We characterize the space of linear functions R n →R which vanish on the lattice points of Λ lying in the half-open unit cube [0, 1) n . We also find an explicit formula for the dimension of the linear span of Λ∩[0,1) n . The results in this paper generalize and are based on the Terminal Lemma of Reid, which is in turn based upon earlier work of Morrison and Stevens on the classification of four dimensional isolated Gorenstein terminal cyclic quotient singularities.
PubDate: 2017-12-09
DOI: 10.1007/s00493-017-3562-7

• Black-box identity testing of depth-4 multilinear circuits
• Authors: Shubhangi Saraf; Ilya Volkovich
Abstract: Abstract We study the problem of identity testing for multilinear ΣΠΣΠ(k) circuits, i.e., multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic identity testing algorithm for such circuits when k=O(1). Our results also hold in the black-box setting. The running time of our algorithm is $${\left( {ns} \right)^{{\text{O}}\left( {{k^3}} \right)}}$$ , where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. The importance of this model arises from [11], where it was shown that derandomizing black-box polynomial identity testing for general depth-4 circuits implies a derandomization of polynomial identity testing (PIT) for general arithmetic circuits. Prior to our work, the best PIT algorithm for multilinear ΣΠΣΠ(k) circuits [31] ran in quasi-polynomial-time, with the running time being $${n^{{\rm O}\left( {{k^6}\log \left( k \right){{\log }^2}s} \right)}}$$ . We obtain our results by showing a strong structural result for multilinear ΣΠΣΠ(k) circuits that compute the zero polynomial. We show that under some mild technical conditions, any gate of such a circuit must compute a sparse polynomial. We then show how to combine the structure theorem with a result by Klivans and Spielman [33], on the identity testing for sparse polynomials, to yield the full result.
PubDate: 2017-12-09
DOI: 10.1007/s00493-016-3460-4

• Minimal normal graph covers
• Authors: David Gajser; Bojan Mohar
Abstract: Abstract A graph is normal if it admits a clique cover C and a stable set cover S such that each clique in C and each stable set in S have a vertex in common. The pair (C,S) is a normal cover of the graph. We present the following extremal property of normal covers. For positive integers c, s, if a graph with n vertices admits a normal cover with cliques of sizes at most c and stable sets of sizes at most s, then c+s≥log2(n). For infinitely many n, we also give a construction of a graph with n vertices that admits a normal cover with cliques and stable sets of sizes less than 0.87log2(n). Furthermore, we show that for all n, there exists a normal graph with n vertices, clique number Θ(log2(n)) and independence number Θ(log2(n)). When c or s are very small, we can describe all normal graphs with the largest possible number of vertices that allow a normal cover with cliques of sizes at most c and stable sets of sizes at most s. However, such extremal graphs remain elusive even for moderately small values of c and s.
PubDate: 2017-08-14
DOI: 10.1007/s00493-017-3559-2

• Edge lower bounds for list critical graphs, via discharging
• Authors: Daniel W. Cranston; Landon Rabern
Abstract: Abstract A graph G is k-critical if G is not (k − 1)-colorable, but every proper subgraph of G is (k − 1)-colorable. A graph G is k-choosable if G has an L-coloring from every list assignment L with L(v) =k for all v, and a graph G is k-list-critical if G is not (k−1)-choosable, but every proper subgraph of G is (k−1)-choosable. The problem of determining the minimum number of edges in a k-critical graph with n vertices has been widely studied, starting with work of Gallai and culminating with the seminal results of Kostochka and Yancey, who essentially solved the problem. In this paper, we improve the best known lower bound on the number of edges in a k-list-critical graph. In fact, our result on k-list-critical graphs is derived from a lower bound on the number of edges in a graph with Alon–Tarsi number at least k. Our proof uses the discharging method, which makes it simpler and more modular than previous work in this area.
PubDate: 2017-08-14
DOI: 10.1007/s00493-016-3584-6

• Count matroids of group-labeled graphs
• Authors: Rintaro Ikeshita; Shin-ichi Tanigawa
Abstract: Abstract A graph G = (V, E) is called (k, ℓ)-sparse if F ≤ k V (F) − ℓ for any nonempty F ⊆ E, where V (F) denotes the set of vertices incident to F. It is known that the family of the edge sets of (k, ℓ)-sparse subgraphs forms the family of independent sets of a matroid, called the (k, ℓ)-count matroid of G. In this paper we shall investigate lifts of the (k, ℓ)- count matroids by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids whose independence condition is described as a count condition of the form F ≤ k V (F) −ℓ+α ψ (F) for some function α ψ determined by a given group labeling ψ on E.
PubDate: 2017-08-14
DOI: 10.1007/s00493-016-3469-8

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327

Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs