Subjects -> MATHEMATICS (Total: 1100 journals)     - APPLIED MATHEMATICS (88 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (812 journals)    - MATHEMATICS (GENERAL) (43 journals)    - NUMERICAL ANALYSIS (24 journals)    - PROBABILITIES AND MATH STATISTICS (110 journals) MATHEMATICS (812 journals)                  1 2 3 4 5 | Last

1 2 3 4 5 | Last

Similar Journals
 Combinatorics, Probability and ComputingJournal Prestige (SJR): 0.839 Citation Impact (citeScore): 1Number of Followers: 4      Hybrid journal (It can contain Open Access articles) ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163 Published by Cambridge University Press  [388 journals]
• Monochromatic trees in random tournaments
• Authors: Matija Bucić; Sven Heberle, Shoham Letzter, Benny Sudakov
Pages: 318 - 345
Abstract: We prove that, with high probability, in every 2-edge-colouring of the random tournament on n vertices there is a monochromatic copy of every oriented tree of order $O(n{\rm{/}}\sqrt {{\rm{log}} \ n} )$ . This generalizes a result of the first, third and fourth authors, who proved the same statement for paths, and is tight up to a constant factor.
PubDate: 2020-05-01T00:00:00.000Z
DOI: 10.1017/S0963548319000373
Issue No: Vol. 29, No. 3 (2020)

• The replica symmetric phase of random constraint satisfaction problems
• Authors: Amin Coja-Oghlan; Tobias Kapetanopoulos, Noela Müller
Pages: 346 - 422
Abstract: Random constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala et al. 2007, Proc. Nat. Acad. Sci.), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g. Banks et al. 2016, Proc. 29th COLT).
PubDate: 2020-05-01T00:00:00.000Z
DOI: 10.1017/S0963548319000440
Issue No: Vol. 29, No. 3 (2020)

• k+=+r+++1+and+k+=+r+++2&rft.title=Combinatorics,+Probability+and+Computing&rft.issn=0963-5483&rft.date=2020&rft.volume=29&rft.spage=423&rft.epage=435&rft.aulast=Ergemlidze&rft.aufirst=Beka&rft.au=Beka+Ergemlidze&rft.au=Ervin+Győri,+Abhishek+Methuku,+Nika+Salia,+Casey+Tompkins,+Oscar+Zamora&rft_id=info:doi/10.1017/S0963548319000415">Avoiding long Berge cycles: the missing cases k = r + 1 and k = r + 2
• Authors: Beka Ergemlidze; Ervin Győri, Abhishek Methuku, Nika Salia, Casey Tompkins, Oscar Zamora
Pages: 423 - 435
Abstract: The maximum size of an r-uniform hypergraph without a Berge cycle of length at least k has been determined for all k ≥ r + 3 by Füredi, Kostochka and Luo and for k < r (and k = r, asymptotically) by Kostochka and Luo. In this paper we settle the remaining cases: k = r + 1 and k = r + 2, proving a conjecture of Füredi, Kostochka and Luo.
PubDate: 2020-05-01T00:00:00.000Z
DOI: 10.1017/S0963548319000415
Issue No: Vol. 29, No. 3 (2020)

• C2k-free+graphs+and+a+problem+of+Kühn+and+Osthus&rft.title=Combinatorics,+Probability+and+Computing&rft.issn=0963-5483&rft.date=2020&rft.volume=29&rft.spage=436&rft.epage=454&rft.aulast=Grósz&rft.aufirst=Dániel&rft.au=Dániel+Grósz&rft.au=Abhishek+Methuku,+Casey+Tompkins&rft_id=info:doi/10.1017/S0963548319000452">On subgraphs of C2k-free graphs and a problem of Kühn and Osthus
• Authors: Dániel Grósz; Abhishek Methuku, Casey Tompkins
Pages: 436 - 454
Abstract: Let c denote the largest constant such that every C6-free graph G contains a bipartite and C4-free subgraph having a fraction c of edges of G. Győri, Kensell and Tompkins showed that 3/8 ⩽ c ⩽ 2/5. We prove that c = 38. More generally, we show that for any ε > 0, and any integer k ⩾ 2, there is a C2k-free graph $G'$ which does not contain a bipartite subgraph of girth greater than 2k with more than a fraction $$\Bigl(1-\frac{1}{2^{2k-2}}\Bigr)\frac{2}{2k-1}(1+\varepsilon)$$ of the edges of $G'$ . There also exists a C2k-free graph $G''$ which does not contain a bipartite and C4-free subgraph with more than a fraction $$\Bigl(1-\frac{1}{2^{k-1}}\Bigr)\frac{1}{k-1}(1+\varepsilon)$$ of the edges of $G''$ .One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdős. For any ε > 0, and any integers a, b, k ⩾ 2, there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colourable subhypergraph with more than a fraction $$\Bigl(1-\frac{1}{b^{a-1}}\Bigr)(1+\varepsilon)$$ of the hyperedges of H. We also prove further generalizations of this theorem.In addition, we give a new and very short proof of a result of Kühn and Osthus, which states that every bipartite C2k-free graph G contains a C4-free subgraph with at least a fraction 1/(k−1) of the edges of G. We also answer a question of Kühn and Osthus about C2
PubDate: 2020-05-01T00:00:00.000Z
DOI: 10.1017/S0963548319000452
Issue No: Vol. 29, No. 3 (2020)

• Minimax functions on Galton–Watson trees
• Authors: James B. Martin; Roman Stasiński
Pages: 455 - 484
Abstract: We consider the behaviour of minimax recursions defined on random trees. Such recursions give the value of a general class of two-player combinatorial games. We examine in particular the case where the tree is given by a Galton–Watson branching process, truncated at some depth 2n, and the terminal values of the level 2n nodes are drawn independently from some common distribution. The case of a regular tree was previously considered by Pearl, who showed that as n → ∞ the value of the game converges to a constant, and by Ali Khan, Devroye and Neininger, who obtained a distributional limit under a suitable rescaling.For a general offspring distribution, there is a surprisingly rich variety of behaviour: the (unrescaled) value of the game may converge to a constant, or to a discrete limit with several atoms, or to a continuous distribution. We also give distributional limits under suitable rescalings in various cases.We also address questions of endogeny. Suppose the game is played on a tree with many levels, so that the terminal values are far from the root. To be confident of playing a good first move, do we need to see the whole tree and its terminal values, or can we play close to optimally by inspecting just the first few levels of the tree' The answers again depend in an interesting way on the offspring distribution.We also mention several open questions.
PubDate: 2020-05-01T00:00:00.000Z
DOI: 10.1017/S0963548319000403
Issue No: Vol. 29, No. 3 (2020)

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