Journal: Combinatorics, Probability & Computing

Abbreviation

Publisher

Cambridge University Press

Journal Volumes

ISSN

0963-5483
1469-2163

Description

Filters

Reset filters

Search Results

Publications1 - 10 of 61
  • Universal geometric graphs
    Item type: Journal Article
    Frati, Fabrizio; Hoffmann, Michael; Tóth, Csaba D. (2023)
    Combinatorics, Probability & Computing
    We extend the notion of universal graphs to a geometric setting. A geometric graph is universal for a class H of planar graphs if it contains an embedding, that is, a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n -vertex forests; this generalises a well-known result by Chung and Graham, which states that there exists an (abstract) graph with n vertices and O(nlogn) edges that contains every n -vertex forest as a subgraph. The upper bound of O(nlogn) edges cannot be improved, even if more than n vertices are allowed. We also prove that every n -vertex convex geometric graph that is universal for n -vertex outerplanar graphs has a near-quadratic number of edges, namely Ωh(n2−1/h) , for every positive integer h ; this almost matches the trivial O(n2) upper bound given by the n -vertex complete convex geometric graph. Finally, we prove that there exists an n -vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n -vertex caterpillars.
  • A linear threshold for uniqueness of solutions to random Jigsaw puzzles
    Item type: Journal Article
    Martinsson, Anders (2019)
    Combinatorics, Probability & Computing
    We consider a problem introduced by Mossel and Ross (‘Shotgun assembly of labeled graphs’, arXiv:1504.07682). Suppose a random n × n jigsaw puzzle is constructed by independently and uniformly choosing the shape of each ‘jig’ from q possibilities. We are given the shuffled pieces. Then, depending on q, what is the probability that we can reassemble the puzzle uniquely? We say that two solutions of a puzzle are similar if they only differ by a global rotation of the puzzle, permutation of duplicate pieces, and rotation of rotationally symmetric pieces. In this paper, we show that, with high probability, such a puzzle has at least two non-similar solutions when 2 $\leq$ q $\leq$ 2e$^{−1/2}$n, all solutions are similar when q $\geq$ (2 + ε)n, and the solution is unique when q =ω(n).
  • Deciding Relaxed Two-Colourability: A Hardness Jump
    Item type: Conference Paper
    Berke, R.; Szabo, T. (2009)
    Combinatorics, Probability & Computing
  • On the size-Ramsey number of grids
    Item type: Journal Article
    Conlon, David; Nenadov, Rajko; Trujić, Miloš (2023)
    Combinatorics, Probability & Computing
  • Mastermind with a linear number of queries
    Item type: Journal Article
    Martinsson, Anders; Su, Pascal (2024)
    Combinatorics, Probability & Computing
  • Simplifying Inclusion–Exclusion Formulas
    Item type: Journal Article
    Goaoc, Xavier; Matoušek, Jiří; Paták, Pavel; et al. (2015)
    Combinatorics, Probability & Computing
  • Improved bound for improper colourings of graphs with no odd clique minor
    Item type: Journal Article
    Steiner, Raphael (2023)
    Combinatorics, Probability & Computing
    Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd K-t-minor is properly (t - 1)-colourable. This is known as the Odd Hadwiger's conjecture. We prove a relaxation of the above conjecture, namely we show that every graph with no odd K-t-minor admits a vertex (2t - 2)-colouring such that all monochromatic components have size at most inverted right perpendicular1/2 (t - 2)inverted left perpendicular. The bound on the number of colours is optimal up to a factor of 2, improves previous bounds for the same problem by Kawarabayashi (2008, Combin. Probab. Comput. 17 815-821), Kang and Oum (2019, Combin. Probab. Comput. 28 740-754), Liu and Wood (2021, arXiv preprint, arXiv:1905.09495), and strengthens a result by van den Heuvel and Wood (2018, J. Lond. Math. Soc. 98 129-148), who showed that the above conclusion holds under the more restrictive assumption that the graph is K-t-minor-free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on t was given by a function arising from the graph minor structure theorem of Robertson and Seymour. Our short proof combines the method by van den Heuvel and Wood for K-t-minor-free graphs with some additional ideas, which make the extension to odd K-t-minor-free graphs possible.
  • Anagram-Free Colourings of Graphs
    Item type: Journal Article
    Kamčev, Nina; Łuczak, Tomasz; Sudakov, Benny (2018)
    Combinatorics, Probability & Computing
  • Tail estimates for sums of variables sampled by a random walk
    Item type: Journal Article
    Wagner, Roy (2008)
    Combinatorics, Probability & Computing
    We prove tail estimates for variables of the form P i f(Xi), where (Xi)I is a sequence of states drawn from a reversible Markov chain, or, equivalently, from a random walk on an undirected graph. The estimates are in terms of the range of the function f, its variance, and the spectrum of the graph. The purpose of our estimates is to determine the number of chain/walk samples which are required for approximating the expectation of a distribution on vertices of a graph, especially an expander. The estimates must therefore provide information for fixed number of samples (as in Gillman’s [4]) rather than just asymptotic information. Our proofs are more elementary than other proofs in the literature, and our results are sharper. We obtain Bernstein and Bennett-type inequalities, as well as an inequality for subgaussian variables.
  • A generalization of Bondy's pancyclicity theorem
    Item type: Journal Article
    Draganić, Nemanja; Munhá Correia, David; Sudakov, Benny (2024)
    Combinatorics, Probability & Computing
    The bipartite independence number of a graph G, denoted as a(G), is the minimal number k such that there exist positive integers a and b with a + b = k + 1 with the property that for any two disjoint sets A, B ⊆ V(G) with |A| = a and |B| = b, there is an edge between A and B. McDiarmid and Yolov showed that if δ(G) ≥ a(G) then G is Hamiltonian, extending the famous theorem of Dirac which states that if δ(G) ≥ |G|/2 then G is Hamiltonian. In 1973, Bondy showed that, unless G is a complete bipartite graph, Dirac's Hamiltonicity condition als implies pancyclicity, i.e., existence of cycles of all the lengths from 3 up to n. In this paper, weh show that δ(G) ≥ a(G) implies that G is pancyclic or that G = Kₙ/₂, ₙ/₂, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.
Publications1 - 10 of 61