Subjects -> MATHEMATICS (Total: 1074 journals)     - APPLIED MATHEMATICS (86 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (793 journals)    - MATHEMATICS (GENERAL) (43 journals)    - NUMERICAL ANALYSIS (23 journals)    - PROBABILITIES AND MATH STATISTICS (106 journals) MATHEMATICS (793 journals)                  1 2 3 4 | Last

1 2 3 4 | 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  [386 journals]
• On the Chromatic Number of Matching Kneser Graphs
• Authors: Meysam Alishahi; Hajiabolhassan Hossein
Pages: 1 - 21
Abstract: In an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker’s lemma, an equivalent combinatorial version of the Borsuk–Ulam theorem, to prove that the altermatic number is a lower bound for chromatic number. A matching Kneser graph is a graph whose vertex set consists of all matchings of a specified size in a host graph and two vertices are adjacent if their corresponding matchings are edge-disjoint. Some well-known families of graphs such as Kneser graphs, Schrijver graphs and permutation graphs can be represented by matching Kneser graphs. In this paper, unifying and generalizing some earlier works by Lovász (1978) and Schrijver (1978), we determine the chromatic number of a large family of matching Kneser graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching Kneser graphs in terms of the generalized Turán number of matchings.
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000178
Issue No: Vol. 29, No. 1 (2020)

• Long Monotone Trails in Random Edge-Labellings of Random Graphs
• Authors: Omer Angel; Asaf Ferber, Benny Sudakov, Vincent Tassion
Pages: 22 - 30
Abstract: Given a graph G and a bijection f : E(G) → {1, 2,…,e(G)}, we say that a trail/path in G is f-increasing if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is n-1, and the case of a path is still wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path.In this paper we consider the random graph G = Gn,p with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of Kn has w.h.p. an increasing trail of length (1-o(1))en, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with p = o(1).
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S096354831900018X
Issue No: Vol. 29, No. 1 (2020)

• On sets of points with few odd secants
• Authors: Simeon Ball; Bence Csajbók
Pages: 31 - 43
Abstract: We prove that, for q odd, a set of q + 2 points in the projective plane over the field with q elements has at least 2q − c odd secants, where c is a constant and an odd secant is a line incident with an odd number of points of the set.
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000245
Issue No: Vol. 29, No. 1 (2020)

• Minimizing the number of 5-cycles in graphs with given edge-density
• Authors: Patrick Bennett; Andrzej Dudek, Bernard Lidický, Oleg Pikhurko
Pages: 44 - 67
Abstract: Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size $(1 - 1/k) \left( {\matrix{n \cr 2 }} \right)$ , where k ≥ 3 is an integer, contains at least $$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$ copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000257
Issue No: Vol. 29, No. 1 (2020)

• Expansion of Percolation Critical Points for Hamming Graphs
• Authors: Lorenzo Federico; Remco Van Der Hofstad, Frank Den Hollander, Tim Hulshof
Pages: 68 - 100
Abstract: The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let ${m=d(n-1)}$ be the degree and $V = n^d$ be the number of vertices of H(d, n). Let $p_c^{(d)}$ be the critical point for bond percolation on H(d, n). We show that, for $d \in \mathbb{N}$ fixed and $n \to \infty$ , $$p_c^{(d)} = {1 \over m} + {{2{d^2} - 1} \over {2{{(d - 1)}^2}}}{1 \over {{m^2}}} + O({m^{ - 3}}) + O({m^{ - 1}}{V^{ - 1/3}}),$$ which extends the asymptotics found in [10] by one order. The term $O(m^{-1}V^{-1/3})$ is the width of the critical window. For $d=4,5,6$ we have $m^{-3} =O(m^{-1}V^{-1/3})$ , and so the above formula represents the full asymptotic expansion of $p_c^{(d)}$ . In [16] we show that this formula...
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000208
Issue No: Vol. 29, No. 1 (2020)

• On Ramsey numbers of hedgehogs
• Authors: Jacob Fox; Ray Li
Pages: 101 - 112
Abstract: The hedgehog Ht is a 3-uniform hypergraph on vertices $1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$ such that, for any pair (i, j) with 1 ≤ i < j ≤ t, there exists a unique vertex k > t such that {i, j, k} is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog Ht is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r(Ht) = O(t2 ln t).
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000312
Issue No: Vol. 29, No. 1 (2020)

• On Komlós’ tiling theorem in random graphs
• Authors: Rajko Nenadov; Nemanja Škorić
Pages: 113 - 127
Abstract: Given graphs G and H, a family of vertex-disjoint copies of H in G is called an H-tiling. Conlon, Gowers, Samotij and Schacht showed that for a given graph H and a constant γ>0, there exists C>0 such that if $p \ge C{n^{ - 1/{m_2}(H)}}$ , then asymptotically almost surely every spanning subgraph G of the random graph í?¯?¢(n, p) with minimum degree at least $\delta (G) \ge (1 - \frac{1}{{{\chi _{{\rm{cr}}}}(H)}} + \gamma )np$ contains an H-tiling that covers all but at most γn vertices. Here, χcr(H) denotes the critical chromatic number, a parameter introduced by Komlós, and m2(H) is the 2-density of H. We show that this theorem can be bootstrapped to obtain an H-tiling covering all but at most $\gamma {(C/p)^{{m_2}(H)}}$ vertices, which is strictly smaller when $p \ge C{n^{ - 1/{m_2}(H)}}$ . In the case where H = K3, this answers the question of Balogh, Lee and Samotij. Furthermore, for an arbitrary graph H we give an upper bound on p for which some leftover is unavoidable and a bound on the size of a largest H -tiling for p below this value.
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000129
Issue No: Vol. 29, No. 1 (2020)

• Extensions of the Erdős–Gallai theorem and Luo’s theorem
• Authors: Bo Ning; Xing Peng
Pages: 128 - 136
Abstract: The famous Erdős–Gallai theorem on the Turán number of paths states that every graph with n vertices and m edges contains a path with at least (2m)/n edges. In this note, we first establish a simple but novel extension of the Erdős–Gallai theorem by proving that every graph G contains a path with at least $${{(s + 1){N_{s + 1}}(G)} \over {{N_s}(G)}} + s - 1$$ edges, where Nj(G) denotes the number of j-cliques in G for 1≤ j ≤ ω(G). We also construct a family of graphs which shows our extension improves the estimate given by the Erdős–Gallai theorem. Among applications, we show, for example, that the main results of [20], which are on the maximum possible number of s-cliques in an n-vertex graph without a path with ℓ vertices (and without cycles of length at least c), can be easily deduced from this extension. Indeed, to prove these results, Luo [20] generalized a classical theorem of Kopylov and established a tight upper bound on the number of s-cliques in an n-vertex 2-connected graph with circumference less than c. We prove a similar result for an n-vertex 2-connected graph with circumference less than c and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs.
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000269
Issue No: Vol. 29, No. 1 (2020)

• The Infinite limit of random permutations avoiding patterns of length
three
• Authors: Ross G. Pinsky
Pages: 137 - 152
Abstract: For $$\tau \in {S_3}$$ , let $$\mu _n^\tau$$ denote the uniformly random probability measure on the set of $$\tau$$ -avoiding permutations in $${S_n}$$ . Let $${\mathbb {N}^*} = {\mathbb {N}} \cup \{ \infty \}$$ with an appropriate metric and denote by $$S({\mathbb{N}},{\mathbb{N}^*})$$ the compact metric space consisting of functions $$\sigma {\rm{ = }}\{ {\sigma _i}\} _{i = 1}^\infty {\rm{ }}$$ from $$\mathbb {N}$$ to $${\mathbb {N}^ * }$$ which are injections when restricted to $${\sigma ^{ - 1}}(\mathbb {N})$$ ; that is, if $${\sigma _i}{\rm{ = }}{\sigma _j}$$
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000270
Issue No: Vol. 29, No. 1 (2020)

• The Induced Removal Lemma in Sparse Graphs
• Authors: Shachar Sapir; Asaf Shapira
Pages: 153 - 162
Abstract: The induced removal lemma of Alon, Fischer, Krivelevich and Szegedy states that if an n-vertex graph G is ε-far from being induced H-free then G contains δH(ε) · nh induced copies of H. Improving upon the original proof, Conlon and Fox proved that 1/δH(ε)is at most a tower of height poly(1/ε), and asked if this bound can be further improved to a tower of height log(1/ε). In this paper we obtain such a bound for graphs G of density O(ε). We actually prove a more general result, which, as a special case, also gives a new proof of Fox’s bound for the (non-induced) removal lemma.
PubDate: 2020-01-01T00:00:00.000Z
DOI: 10.1017/S0963548319000233
Issue No: Vol. 29, No. 1 (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