Subjects -> COMPUTER SCIENCE (Total: 2313 journals)
    - ANIMATION AND SIMULATION (33 journals)
    - ARTIFICIAL INTELLIGENCE (133 journals)
    - AUTOMATION AND ROBOTICS (116 journals)
    - CLOUD COMPUTING AND NETWORKS (75 journals)
    - COMPUTER ARCHITECTURE (11 journals)
    - COMPUTER ENGINEERING (12 journals)
    - COMPUTER GAMES (23 journals)
    - COMPUTER PROGRAMMING (25 journals)
    - COMPUTER SCIENCE (1305 journals)
    - COMPUTER SECURITY (59 journals)
    - DATA BASE MANAGEMENT (21 journals)
    - DATA MINING (50 journals)
    - E-BUSINESS (21 journals)
    - E-LEARNING (30 journals)
    - ELECTRONIC DATA PROCESSING (23 journals)
    - IMAGE AND VIDEO PROCESSING (42 journals)
    - INFORMATION SYSTEMS (109 journals)
    - INTERNET (111 journals)
    - SOCIAL WEB (61 journals)
    - SOFTWARE (43 journals)
    - THEORY OF COMPUTING (10 journals)

COMPUTER SCIENCE (1305 journals)                  1 2 3 4 5 6 7 | Last

Showing 1 - 200 of 872 Journals sorted alphabetically
3D Printing and Additive Manufacturing     Full-text available via subscription   (Followers: 27)
Abakós     Open Access   (Followers: 3)
ACM Computing Surveys     Hybrid Journal   (Followers: 29)
ACM Inroads     Full-text available via subscription   (Followers: 1)
ACM Journal of Computer Documentation     Free   (Followers: 4)
ACM Journal on Computing and Cultural Heritage     Hybrid Journal   (Followers: 5)
ACM Journal on Emerging Technologies in Computing Systems     Hybrid Journal   (Followers: 11)
ACM SIGACCESS Accessibility and Computing     Free   (Followers: 2)
ACM SIGAPP Applied Computing Review     Full-text available via subscription  
ACM SIGBioinformatics Record     Full-text available via subscription  
ACM SIGEVOlution     Full-text available via subscription  
ACM SIGHIT Record     Full-text available via subscription  
ACM SIGHPC Connect     Full-text available via subscription  
ACM SIGITE Newsletter     Open Access   (Followers: 1)
ACM SIGMIS Database: the DATABASE for Advances in Information Systems     Hybrid Journal  
ACM SIGUCCS plugged in     Full-text available via subscription  
ACM SIGWEB Newsletter     Full-text available via subscription   (Followers: 4)
ACM Transactions on Accessible Computing (TACCESS)     Hybrid Journal   (Followers: 3)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 13)
ACM Transactions on Applied Perception (TAP)     Hybrid Journal   (Followers: 3)
ACM Transactions on Architecture and Code Optimization (TACO)     Hybrid Journal   (Followers: 9)
ACM Transactions on Asian and Low-Resource Language Information Processing (TALLIP)     Hybrid Journal  
ACM Transactions on Autonomous and Adaptive Systems (TAAS)     Hybrid Journal   (Followers: 10)
ACM Transactions on Computation Theory (TOCT)     Hybrid Journal   (Followers: 11)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 5)
ACM Transactions on Computer Systems (TOCS)     Hybrid Journal   (Followers: 19)
ACM Transactions on Computer-Human Interaction     Hybrid Journal   (Followers: 15)
ACM Transactions on Computing Education (TOCE)     Hybrid Journal   (Followers: 9)
ACM Transactions on Computing for Healthcare     Hybrid Journal  
ACM Transactions on Cyber-Physical Systems (TCPS)     Hybrid Journal   (Followers: 1)
ACM Transactions on Design Automation of Electronic Systems (TODAES)     Hybrid Journal   (Followers: 5)
ACM Transactions on Economics and Computation     Hybrid Journal  
ACM Transactions on Embedded Computing Systems (TECS)     Hybrid Journal   (Followers: 4)
ACM Transactions on Information Systems (TOIS)     Hybrid Journal   (Followers: 18)
ACM Transactions on Intelligent Systems and Technology (TIST)     Hybrid Journal   (Followers: 11)
ACM Transactions on Interactive Intelligent Systems (TiiS)     Hybrid Journal   (Followers: 6)
ACM Transactions on Internet of Things     Hybrid Journal   (Followers: 2)
ACM Transactions on Modeling and Performance Evaluation of Computing Systems (ToMPECS)     Hybrid Journal  
ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP)     Hybrid Journal   (Followers: 10)
ACM Transactions on Parallel Computing     Full-text available via subscription  
ACM Transactions on Reconfigurable Technology and Systems (TRETS)     Hybrid Journal   (Followers: 6)
ACM Transactions on Sensor Networks (TOSN)     Hybrid Journal   (Followers: 9)
ACM Transactions on Social Computing     Hybrid Journal  
ACM Transactions on Spatial Algorithms and Systems (TSAS)     Hybrid Journal   (Followers: 1)
ACM Transactions on Speech and Language Processing (TSLP)     Hybrid Journal   (Followers: 11)
ACM Transactions on Storage     Hybrid Journal  
ACS Applied Materials & Interfaces     Hybrid Journal   (Followers: 39)
Acta Informatica Malaysia     Open Access  
Acta Universitatis Cibiniensis. Technical Series     Open Access   (Followers: 1)
Ad Hoc Networks     Hybrid Journal   (Followers: 12)
Adaptive Behavior     Hybrid Journal   (Followers: 8)
Additive Manufacturing Letters     Open Access   (Followers: 3)
Advanced Engineering Materials     Hybrid Journal   (Followers: 32)
Advanced Science Letters     Full-text available via subscription   (Followers: 9)
Advances in Adaptive Data Analysis     Hybrid Journal   (Followers: 9)
Advances in Artificial Intelligence     Open Access   (Followers: 31)
Advances in Catalysis     Full-text available via subscription   (Followers: 7)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 20)
Advances in Computer Engineering     Open Access   (Followers: 13)
Advances in Computer Science : an International Journal     Open Access   (Followers: 18)
Advances in Computing     Open Access   (Followers: 3)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 52)
Advances in Engineering Software     Hybrid Journal   (Followers: 26)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 19)
Advances in Human-Computer Interaction     Open Access   (Followers: 19)
Advances in Image and Video Processing     Open Access   (Followers: 20)
Advances in Materials Science     Open Access   (Followers: 19)
Advances in Multimedia     Open Access   (Followers: 1)
Advances in Operations Research     Open Access   (Followers: 13)
Advances in Remote Sensing     Open Access   (Followers: 59)
Advances in Science and Research (ASR)     Open Access   (Followers: 8)
Advances in Technology Innovation     Open Access   (Followers: 5)
AEU - International Journal of Electronics and Communications     Hybrid Journal   (Followers: 8)
African Journal of Information and Communication     Open Access   (Followers: 6)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 5)
AI EDAM     Hybrid Journal   (Followers: 2)
Air, Soil & Water Research     Open Access   (Followers: 6)
AIS Transactions on Human-Computer Interaction     Open Access   (Followers: 5)
Al-Qadisiyah Journal for Computer Science and Mathematics     Open Access   (Followers: 2)
AL-Rafidain Journal of Computer Sciences and Mathematics     Open Access   (Followers: 3)
Algebras and Representation Theory     Hybrid Journal  
Algorithms     Open Access   (Followers: 13)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 8)
American Journal of Computational Mathematics     Open Access   (Followers: 6)
American Journal of Information Systems     Open Access   (Followers: 4)
American Journal of Sensor Technology     Open Access   (Followers: 2)
Analog Integrated Circuits and Signal Processing     Hybrid Journal   (Followers: 15)
Animation Practice, Process & Production     Hybrid Journal   (Followers: 4)
Annals of Combinatorics     Hybrid Journal   (Followers: 3)
Annals of Data Science     Hybrid Journal   (Followers: 14)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 16)
Annals of Pure and Applied Logic     Open Access   (Followers: 4)
Annals of Software Engineering     Hybrid Journal   (Followers: 12)
Annual Reviews in Control     Hybrid Journal   (Followers: 7)
Anuario Americanista Europeo     Open Access  
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 3)
Applied and Computational Harmonic Analysis     Full-text available via subscription  
Applied Artificial Intelligence: An International Journal     Hybrid Journal   (Followers: 17)
Applied Categorical Structures     Hybrid Journal   (Followers: 4)
Applied Clinical Informatics     Hybrid Journal   (Followers: 4)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 16)
Applied Computer Systems     Open Access   (Followers: 6)
Applied Computing and Geosciences     Open Access   (Followers: 3)
Applied Mathematics and Computation     Hybrid Journal   (Followers: 31)
Applied Medical Informatics     Open Access   (Followers: 11)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 4)
Applied Soft Computing     Hybrid Journal   (Followers: 13)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 5)
Applied System Innovation     Open Access   (Followers: 1)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4)
Archive of Numerical Software     Open Access  
Archives and Museum Informatics     Hybrid Journal   (Followers: 97)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 5)
arq: Architectural Research Quarterly     Hybrid Journal   (Followers: 7)
Array     Open Access   (Followers: 1)
Artifact : Journal of Design Practice     Open Access   (Followers: 8)
Artificial Life     Hybrid Journal   (Followers: 7)
Asian Journal of Computer Science and Information Technology     Open Access   (Followers: 3)
Asian Journal of Control     Hybrid Journal  
Asian Journal of Research in Computer Science     Open Access   (Followers: 4)
Assembly Automation     Hybrid Journal   (Followers: 2)
Automatic Control and Computer Sciences     Hybrid Journal   (Followers: 6)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Automatica     Hybrid Journal   (Followers: 13)
Automatika : Journal for Control, Measurement, Electronics, Computing and Communications     Open Access  
Automation in Construction     Hybrid Journal   (Followers: 8)
Balkan Journal of Electrical and Computer Engineering     Open Access  
Basin Research     Hybrid Journal   (Followers: 7)
Behaviour & Information Technology     Hybrid Journal   (Followers: 32)
BenchCouncil Transactions on Benchmarks, Standards, and Evaluations     Open Access   (Followers: 4)
Big Data and Cognitive Computing     Open Access   (Followers: 5)
Big Data Mining and Analytics     Open Access   (Followers: 10)
Biodiversity Information Science and Standards     Open Access   (Followers: 1)
Bioinformatics     Hybrid Journal   (Followers: 217)
Bioinformatics Advances : Journal of the International Society for Computational Biology     Open Access   (Followers: 1)
Biomedical Engineering     Hybrid Journal   (Followers: 11)
Biomedical Engineering and Computational Biology     Open Access   (Followers: 11)
Briefings in Bioinformatics     Hybrid Journal   (Followers: 43)
British Journal of Educational Technology     Hybrid Journal   (Followers: 93)
Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics     Open Access  
c't Magazin fuer Computertechnik     Full-text available via subscription   (Followers: 1)
Cadernos do IME : Série Informática     Open Access  
CALCOLO     Hybrid Journal  
CALICO Journal     Full-text available via subscription   (Followers: 1)
Calphad     Hybrid Journal  
Canadian Journal of Electrical and Computer Engineering     Full-text available via subscription   (Followers: 14)
Catalysis in Industry     Hybrid Journal  
CCF Transactions on High Performance Computing     Hybrid Journal  
CCF Transactions on Pervasive Computing and Interaction     Hybrid Journal  
CEAS Space Journal     Hybrid Journal   (Followers: 6)
Cell Communication and Signaling     Open Access   (Followers: 3)
Central European Journal of Computer Science     Hybrid Journal   (Followers: 4)
CERN IdeaSquare Journal of Experimental Innovation     Open Access  
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 1)
Chaos, Solitons & Fractals : X     Open Access   (Followers: 1)
Chemometrics and Intelligent Laboratory Systems     Hybrid Journal   (Followers: 13)
ChemSusChem     Hybrid Journal   (Followers: 7)
China Communications     Full-text available via subscription   (Followers: 8)
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
Chip     Full-text available via subscription   (Followers: 3)
Ciencia     Open Access  
CIN : Computers Informatics Nursing     Hybrid Journal   (Followers: 11)
Circuits and Systems     Open Access   (Followers: 16)
CLEI Electronic Journal     Open Access  
Clin-Alert     Hybrid Journal   (Followers: 1)
Clinical eHealth     Open Access  
Cluster Computing     Hybrid Journal   (Followers: 1)
Cognitive Computation     Hybrid Journal   (Followers: 2)
Cognitive Computation and Systems     Open Access  
COMBINATORICA     Hybrid Journal  
Combinatorics, Probability and Computing     Hybrid Journal   (Followers: 4)
Combustion Theory and Modelling     Hybrid Journal   (Followers: 18)
Communication Methods and Measures     Hybrid Journal   (Followers: 12)
Communication Theory     Hybrid Journal   (Followers: 29)
Communications in Algebra     Hybrid Journal   (Followers: 1)
Communications in Partial Differential Equations     Hybrid Journal   (Followers: 2)
Communications of the ACM     Full-text available via subscription   (Followers: 59)
Communications of the Association for Information Systems     Open Access   (Followers: 15)
Communications on Applied Mathematics and Computation     Hybrid Journal   (Followers: 1)
COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering     Hybrid Journal   (Followers: 4)
Complex & Intelligent Systems     Open Access   (Followers: 1)
Complex Adaptive Systems Modeling     Open Access  
Complex Analysis and Operator Theory     Hybrid Journal   (Followers: 2)
Complexity     Hybrid Journal   (Followers: 8)
Computación y Sistemas     Open Access  
Computation     Open Access   (Followers: 1)
Computational and Applied Mathematics     Hybrid Journal   (Followers: 3)
Computational and Mathematical Methods     Hybrid Journal  
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 1)
Computational and Structural Biotechnology Journal     Open Access   (Followers: 1)
Computational and Theoretical Chemistry     Hybrid Journal   (Followers: 11)
Computational Astrophysics and Cosmology     Open Access   (Followers: 6)
Computational Biology and Chemistry     Hybrid Journal   (Followers: 13)
Computational Biology Journal     Open Access   (Followers: 6)
Computational Brain & Behavior     Hybrid Journal   (Followers: 1)
Computational Chemistry     Open Access   (Followers: 3)
Computational Communication Research     Open Access   (Followers: 1)
Computational Complexity     Hybrid Journal   (Followers: 5)
Computational Condensed Matter     Open Access   (Followers: 1)

        1 2 3 4 5 6 7 | Last

Similar Journals
Journal Cover
COMBINATORICA
Journal Prestige (SJR): 1.764
Citation Impact (citeScore): 1
Number of Followers: 0  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1439-6912 - ISSN (Online) 0209-9683
Published by Springer-Verlag Homepage  [2469 journals]
  • A Short Proof of the Blow-Up Lemma for Approximate Decompositions

    • Free pre-print version: Loading...

      Abstract: Abstract Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655–4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi by proving a ‘blow-up lemma for approximate decompositions’ which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kühn and Osthus to prove the tree packing conjecture due to Gyárfás and Lehel from 1976 and Ringel’s conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kühn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications.
      PubDate: 2022-05-19
       
  • Even Maps, the Colin de Verdière Number and Representations of Graphs

    • Free pre-print version: Loading...

      Abstract: Abstract Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on σ(G) which is, in general, tight. Equality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2.
      PubDate: 2022-05-19
       
  • Oriented Cycles in Digraphs of Large Outdegree

    • Free pre-print version: Loading...

      Abstract: Abstract In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ. We prove this conjecture and answer further open questions raised by Aboulker et al.
      PubDate: 2022-05-19
       
  • Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane

    • Free pre-print version: Loading...

      Abstract: Abstract A Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable.
      PubDate: 2022-05-19
       
  • On Bounding the Diameter of a Distance-Regular Graph

    • Free pre-print version: Loading...

      Abstract: Abstract In this note we investigate how to use an initial portion of the intersection array of a distance-regular graph to give an upper bound for the diameter of the graph. We prove three new diameter bounds. Our bounds are tight for the Hamming d-cube, doubled Odd graphs, the Heawood graph, Tutte’s 8-cage and 12-cage, the generalized dodecagons of order (1, 3) and (1, 4), the Biggs-Smith graph, the Pappus graph, the Wells graph, and the dodecahedron.
      PubDate: 2022-04-01
       
  • On Thin Sum-Product Bases

    • Free pre-print version: Loading...

      Abstract: Abstract Besides various asymptotic results on the concept of sum-product bases in the set of non-negative integers ℕ, we investigate by probabilistic arguments the existence of thin sets A, A′ of non-negative integers such that AA + A = ℕ and A′A′ + A′A′ = ℕ.
      PubDate: 2022-04-01
       
  • Stack-Number is Not Bounded by Queue-Number

    • Free pre-print version: Loading...

      Abstract: Abstract We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
      PubDate: 2022-04-01
       
  • A Family of Balanced Generalized Weighing Matrices

    • Free pre-print version: Loading...

      Abstract: Abstract Balanced weighing matrices with parameters $$\left({1 + 18 \cdot {{{9^{m + 1}} - 1} \over 8},{9^{m + 1}},4 \cdot {9^m}} \right),$$ for each nonzero integer m are constructed. This is the first infinite class not belonging to those with classical parameters. It is shown that any balanced weighing matrix is equivalent to a five-class association scheme.
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-021-4774-4
       
  • The Chromatic Number of the Product of 14-Chromatic Graphs Can BE 13

    • Free pre-print version: Loading...

      Abstract: Abstract We show that for any n ≥ 13, there exist graphs with chromatic number larger than n whose product has chromatic number n. Our construction is an adaptation of the construction of counterexamples to Hedetniemi’s conjecture devised by Shitov, and adapted by Zhu to graphs with relatively small chromatic numbers. The new tools we introduce are graphs with minimal colourings that are “wide” in the sense of Simonyi and Tardos, and generalised Mycielskians to settle the case n = 13.
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-021-4781-5
       
  • Fractional Isomorphism of Graphons

    • Free pre-print version: Loading...

      Abstract: Abstract We work out the theory of fractional isomorphism of graphons as a generalization to the classical theory of fractional isomorphism of finite graphs. The generalization is given in terms of homomorphism densities of finite trees and it is characterized in terms of distributions on iterated degree measures, Markov operators, weak isomorphism of a conditional expectation with respect to invariant sub-σ-algebras and isomorphism of certain quotients of given graphons.
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-021-4336-9
       
  • A Combinatorial Bijection on k-Noncrossing Partitions

    • Free pre-print version: Loading...

      Abstract: Abstract For any integer k ≥ 2, we prove combinatorially the following Euler (binomial) transformation identity $${\rm{NC}}_{n + 1}^{(k)}(t) = t\sum\limits_{i = 0}^n {\left({\matrix{n \cr i \cr}} \right)} {\rm{NW}}_i^{(k)}(t),$$ where NC m (k) (t) (resp. NW m (k) (t)) is the sum of weights, tnumber of blocks, of partitions of {1,…,m} without k-crossings (resp. enhanced k-crossings). The special k = 2 and t = 1 case, asserting the Euler transformation of Motzkin numbers are Catalan numbers, was discovered by Donaghey 1977. The result for k = 3 and t = 1, arising naturally in a recent study of pattern avoidance in ascent sequences and inversion sequences, was proved only analytically.
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-021-4262-x
       
  • The Characteristic Polynomial of a Random Matrix

    • Free pre-print version: Loading...

      Abstract: Abstract Form an n × n matrix by drawing entries independently from {±1} (or another fixed nontrivial finitely supported distribution in Z) and let φ be the characteristic polynomial. We show, conditionally on the extended Riemann hypothesis, that with high probability φ is irreducible and Gal(φ) ≥ An.
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-020-4657-0
       
  • The Number of Maximal Independent Sets in the Hamming Cube

    • Free pre-print version: Loading...

      Abstract: Abstract Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically $$2n{2^{N/4}},$$ as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Qn.
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-021-4729-9
       
  • Extractors for Small Zero-Fixing Sources

    • Free pre-print version: Loading...

      Abstract: Abstract Let V ⊆ [n] be a k-element subset of [n]. The uniform distribution on the 2k strings from {0, 1}n that are set to zero outside of V is called an (n, k)-zero-fixing source. An ϵ-extractor for (n, k)-zero-fixing sources is a mapping F: {0, 1}n → {0, 1}m, for some m, such that F(X) is ϵ-close in statistical distance to the uniform distribution on {0, 1}m for every (n, k)-zero-fixing source X. Zero-fixing sources were introduced by Cohen and Shinkar in [7] in connection with the previously studied extractors for bit-fixing sources. They constructed, for every μ > 0, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., Ω(k) bits, from (n, k)-zero-fixing sources where k ≥ (log log n)2+μ. In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for k substantially smaller than log log n. The first extractor works for k ≥ C log log log n, for some constant C. The second extractor extracts a positive fraction of entropy for k ≥ log(i)n for any fixed i ∈ ℕ, where log(i) denotes i-times iterated logarithm. The fraction of extracted entropy decreases with i. The first extractor is a function computable in polynomial time in n; the second one is computable in polynomial time in n when k ≤ α log log n/log log log n, where α is a positive constant. Our results can also be viewed as lower bounds on some Ramsey-type properties. The main difference between the problems about extractors studied here and the standard Ramsey theory is that we study colorings of all subsets of size up to k while in Ramsey theory the sizes are fixed to k. However it is easy to derive results also for coloring of subsets of sizes equal to k. In Corollary 3.1 of Theorem 5.1 we show that for every l ∈ ℕ there exists β < 1 such that for every k and n, n ≤ expl (k), there exists a 2-coloring of k-tuples of elements of [n], \(\psi :\left({\matrix{{[n]} \cr k \cr}} \right) \to \left\{{- 1,1} \right\}\) such that for every V ⊆ [n], V = 2k, we have \(\left {\sum\nolimits_{X \subseteq V,\left X \right = k} {\psi (X)}} \right \le {\beta ^k}\left({\matrix{{2k} \cr k \cr}} \right)\) (Corollary 3.1 is more general — the number of colors may be more than 2).
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-020-4626-7
       
  • Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs
           with c ≤ 12

    • Free pre-print version: Loading...

      Abstract: Abstract We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c ≥ 13 and d ≥ 1, we give first explicit constructions of c-crossing-critical graphs containing arbitrarily many vertices of degree greater than d. We also show that such unbounded degree constructions do not exist for c ≤ 12, precisely, that there exists a constant D such that every c-crossing-critical graph with c ≤ 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c ≤ 12.1
      PubDate: 2022-03-14
      DOI: 10.1007/s00493-021-4285-3
       
  • Ramsey Numbers of Books and Quasirandomness

    • Free pre-print version: Loading...

      Abstract: Abstract The book graph \(B_n^{(k)}\) consists of n copies of Kk+1 joined along a common Kk. The Ramsey numbers of \(B_n^{(k)}\) are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi’s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.
      PubDate: 2022-03-10
      DOI: 10.1007/s00493-021-4409-9
       
  • Computing the Covering Radius of a Polytope with an Application to Lonely
           Runners

    • Free pre-print version: Loading...

      Abstract: Abstract We study the computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed for the lattice translates of the correspondingly dilated polytope to cover the whole space. As our main result, we describe a new algorithm for this problem, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). Motivated by a variant of the famous Lonely Runner Conjecture, we use its geometric interpretation in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points.
      PubDate: 2022-02-18
      DOI: 10.1007/s00493-020-4633-8
       
  • A Hypergraph Turán Problem with No Stability

    • Free pre-print version: Loading...

      Abstract: Abstract A fundamental barrier in extremal hypergraph theory is the presence of many near-extremal constructions with very different structures. Indeed, the classical constructions due to Kostochka imply that the notorious extremal problem for the tetrahedron exhibits this phenomenon assuming Turán’s conjecture. Our main result is to construct a finite family of triple systems \({\cal M}\) , determine its Turán number, and prove that there are two near-extremal \({\cal M}\) -free constructions that are far from each other in edit-distance. This is the first extremal result for a hypergraph family that fails to have a corresponding stability theorem.
      PubDate: 2022-02-18
      DOI: 10.1007/s00493-021-4561-2
       
  • On the Density of C7-Critical Graphs Luke Postle, Evelyne Smith-Roberge

    • Free pre-print version: Loading...

      Abstract: Abstract In 1959, Grötzsch [5] famously proved that every planar graph of girth at least 4 is 3-colourable (or equivalently, admits a homomorphism to C3). A natural generalization of this is the following conjecture: for every positive integer t, every planar graph of girth at least 4t admits a homomorphism to C2t+1. This is in fact the planar dual of a well-known conjecture of Jaeger [7] which states that every 4t-edge-connected graph admits a modulo (2t + 1)-orientation. Though Jaeger’s original conjecture was disproved in [6], Lovász et al. [10] showed that every 6t-edge connected graph admits a modolo (2t + 1)-flow. The latter result implies that every planar graph of girth at least 6t admits a homomorphism to C2t+1. We improve upon this in the t = 3 case, by showing that every planar graph of girth at least 16 admits a homomorphism to C7. We obtain this through a more general result regarding the density of C7-critical graphs: if G is a C7-critical graph with G ∉ {C3, C5}, then \(e(G) \ge {{17v(G) - 2} \over {15}}\) .
      PubDate: 2022-02-18
      DOI: 10.1007/s00493-020-4177-y
       
  • An Analytic Approach to Cardinalities of Sumsets Dávid Matolcsi, Imre Z.
           Ruzsa, George Shakan, Dmitrii Zhelezov

    • Free pre-print version: Loading...

      Abstract: Abstract Let d be a positive integer and U ⊂ ℤd finite. We study $$\beta (U): = \mathop {\inf }\limits_{\mathop {A,B \ne \phi }\limits_{{\rm{finite}}} } {{\left {A + B + U} \right } \over {{{\left A \right }^{1/2}}{{\left B \right }^{1/2}}}},$$ and other related quantities. We employ tensorization, which is not available for the doubling constant, ∣U + U∣/∣U∣. For instance, we show $$\beta (U) = \left U \right ,$$ whenever U is a subset of {0,1}d. Our methods parallel those used for the Prékopa—Leindler inequality, an integral variant of the Brunn—Minkowski inequality.
      PubDate: 2022-01-14
      DOI: 10.1007/s00493-021-4547-0
       
 
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
 


Your IP address: 44.200.74.241
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-