Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract For all integers \(n \ge k > d \ge 1\) , let \(m_{d}(k,n)\) be the minimum integer \(D \ge 0\) such that every k-uniform n-vertex hypergraph \({\mathcal {H}}\) with minimum d-degree \(\delta _{d}({\mathcal {H}})\) at least D has an optimal matching. For every fixed integer \(k \ge 3\) , we show that for \(n \in k \mathbb {N}\) and \(p = \Omega (n^{-k+1} \log n)\) , if \({\mathcal {H}}\) is an n-vertex k-uniform hypergraph with \(\delta _{k-1}({\mathcal {H}}) \ge m_{k-1}(k,n)\) , then a.a.s. its p-random subhypergraph \({\mathcal {H}}_p\) contains a perfect matching. Moreover, for every fixed integer \(d < k\) and \(\gamma > 0\) , we show that the same conclusion holds if \({\mathcal {H}}\) is an n-vertex k-uniform hypergraph with \(\delta _d({\mathcal {H}}) \ge m_{d}(k,n) + \gamma \left( {\begin{array}{c}n - d\\ k - d\end{array}}\right) \) . Both of these results strengthen Johansson, Kahn, and Vu’s seminal solution to Shamir’s problem and can be viewed as “robust” versions of hypergraph Dirac-type results. In addition, we also show that in both cases above, \({\mathcal {H}}\) has at least \(\exp ((1-1/k)n \log n - \Theta (n))\) many perfect matchings, which is best possible up to an \(\exp (\Theta (n))\) factor. PubDate: 2024-08-05 DOI: 10.1007/s00493-024-00116-0
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A pure pair of size t in a graph G is a pair A, B of disjoint subsets of V(G), each of cardinality at least t, such that A is either complete or anticomplete to B. It is known that, for every forest H, every graph on \(n\ge 2\) vertices that does not contain H or its complement as an induced subgraph has a pure pair of size \(\Omega (n)\) ; furthermore, this only holds when H or its complement is a forest. In this paper, we look at pure pairs of size \(n^{1-c}\) , where \(0<c<1\) . Let H be a graph: does every graph on \(n\ge 2\) vertices that does not contain H or its complement as an induced subgraph have a pure pair of size \(\Omega ( G ^{1-c})\) ' The answer is related to the congestion of H, the maximum of \(1-( J -1)/ E(J) \) over all subgraphs J of H with an edge. (Congestion is nonnegative, and equals zero exactly when H is a forest.) Let d be the smaller of the congestions of H and \(\overline{H}\) . We show that the answer to the question above is “yes” if \(d\le c/(9+15c)\) , and “no” if \(d>c\) . PubDate: 2024-08-05 DOI: 10.1007/s00493-024-00117-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number \(s>2\) , we prove that every graph on n vertices with average degree \(d\ge s\) contains a subgraph of average degree at least s on at most \(nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}\) vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with n vertices and average degree at least \(n^{1-\frac{2}{s}+\varepsilon }\) contains a subgraph of average degree at least s on \(O_{\varepsilon ,s}(1)\) vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraëte. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00091-6
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A d-dimensional framework is a pair (G, p), where \(G=(V,E)\) is a graph and p is a map from V to \({\mathbb {R}}^d\) . The length of an edge \(xy\in E\) in (G, p) is the distance between p(x) and p(y). A vertex pair \(\{u,v\}\) of G is said to be globally linked in (G, p) if the distance between p(u) and p(v) is equal to the distance between q(u) and q(v) for every d-dimensional framework (G, q) in which the corresponding edge lengths are the same as in (G, p). We call (G, p) globally rigid in \({\mathbb {R}}^d\) when each vertex pair of G is globally linked in (G, p). A pair \(\{u,v\}\) of vertices of G is said to be weakly globally linked in G in \({\mathbb {R}}^d\) if there exists a generic framework (G, p) in which \(\{u,v\}\) is globally linked. In this paper we first give a sufficient condition for the weak global linkedness of a vertex pair of a \((d+1)\) -connected graph G in \({\mathbb {R}}^d\) and then show that for \(d=2\) it is also necessary. We use this result to obtain a complete characterization of weakly globally linked pairs in graphs in \({\mathbb {R}}^2\) , which gives rise to an algorithm for testing weak global linkedness in the plane in \(O( V ^2)\) time. Our methods lead to a new short proof for the characterization of globally rigid graphs in \({\mathbb {R}}^2\) , and further results on weakly globally linked pairs and globally rigid graphs in the plane and in higher dimensions. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00094-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We prove that every properly edge-colored n-vertex graph with average degree at least \(32(\log 5n)^2\) contains a rainbow cycle, improving upon the \((\log n)^{2+o(1)}\) bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least \(10^5 k^3 n^{1+1/k}\) edges contains a rainbow 2k-cycle, which improves the previous bound \(2^{ck^2}n^{1+1/k}\) obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erdős–Simonovits supersaturation theorem for even cycles, which may be of independent interest. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00101-7
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The problem of Zarankiewicz asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph \(K_{k,k}\) as a subgraph. A classical theorem due to Kővári, Sós, and Turán says that this number of edges is \(O\left( n^{2 - 1/k}\right) \) . An important variant of this problem is the analogous question in bipartite graphs with VC-dimension at most d, where d is a fixed integer such that \(k \ge d \ge 2\) . A remarkable result of Fox et al. (J. Eur. Math. Soc. (JEMS) 19:1785–1810, 2017) with multiple applications in incidence geometry shows that, under this additional hypothesis, the number of edges in a bipartite graph on n vertices and with no copy of \(K_{k,k}\) as a subgraph must be \(O\left( n^{2 - 1/d}\right) \) . This theorem is sharp when \(k=d=2\) , because by design any \(K_{2,2}\) -free graph automatically has VC-dimension at most 2, and there are well-known examples of such graphs with \(\Omega \left( n^{3/2}\right) \) edges. However, it turns out this phenomenon no longer carries through for any larger d. We show the following improved result: the maximum number of edges in bipartite graphs with no copies of \(K_{k,k}\) and VC-dimension at most d is \(o(n^{2-1/d})\) , for every \(k \ge d \ge 3\) . PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00095-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let N be the number of triangles in an Erdős–Rényi graph \({\mathcal {G}}(n,p)\) on n vertices with edge density \(p=d/n,\) where \(d>0\) is a fixed constant. It is well known that N weakly converges to the Poisson distribution with mean \({d^3}/{6}\) as \(n\rightarrow \infty \) . We address the upper tail problem for N, namely, we investigate how fast k must grow, so that \({\mathbb {P}}(N\ge k)\) is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when \(k^{1/3} \log k< (\frac{3}{\sqrt{2}} - {o(1)})^{2/3} \log n\) (sub-critical regime) as well as pin down the tail behavior when \(k^{1/3} \log k> (\frac{3}{\sqrt{2}} + {o(1)})^{2/3} \log n\) (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost k vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately \((6k)^{1/3}\) . This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades and culminating in Harel et al. (Duke Math J 171(10):2089–2192, 2022), which analyzed the problem only in the regime \(p\gg \frac{1}{n}.\) The proofs rely on several novel graph theoretical results which could have other applications. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00086-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The amount of hyperplanes that are needed in order to cover the Boolean cube has been studied in various contexts. Linial and Radhakrishnan introduced the notion of essential covers. An essential cover is a collection of hyperplanes that form a minimal cover of the vertices of the hypercube, and every coordinate is influential in at least one of the hyperplanes. Linial and Radhakrishnan proved using algebraic tools that every essential cover of the n-cube must be of size at least \(\Omega (\sqrt{n})\) . We devise a stronger lower bound method, and show that the size of every essential cover is at least \(\Omega (n^{0.52})\) . This result has implications in proof complexity, because essential covers have been used to prove lower bounds for several proof systems. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00093-4
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc uv in a tournament T is the set of vertices that form a directed triangle with arc uv. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. This holds more generally for oriented graphs with bounded independence number, and we extend our proof from tournaments to this class of dense digraphs. As an application, we prove the equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00098-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these results rely on isoperimetric properties of the underlying host graph. Recently, the authors showed that such a phase transition occurs in a large class of regular high-dimensional product graphs, generalising a classic result for the hypercube. In this paper we give new isoperimetric inequalities for such regular high-dimensional product graphs, which generalise the well-known isoperimetric inequality of Harper for the hypercube, and are asymptotically sharp for a wide range of set sizes. We then use these isoperimetric properties to investigate the structure of the giant component \(L_1\) in supercritical percolation on these product graphs, that is, when \(p=\frac{1+\epsilon }{d}\) , where d is the degree of the product graph and \(\epsilon >0\) is a small enough constant. We show that typically \(L_1\) has edge-expansion \(\Omega \left( \frac{1}{d\ln d}\right) \) . Furthermore, we show that \(L_1\) likely contains a linear-sized subgraph with vertex-expansion \(\Omega \left( \frac{1}{d\ln d}\right) \) . These results are best possible up to the logarithmic factor in d. Using these likely expansion properties, we determine, up to small polylogarithmic factors in d, the likely diameter of \(L_1\) as well as the typical mixing time of a lazy random walk on \(L_1\) . Furthermore, we show the likely existence of a cycle of length \(\Omega \left( \frac{n}{d\ln d}\right) \) . These results not only generalise, but also improve substantially upon the known bounds in the case of the hypercube, where in particular the likely diameter and typical mixing time of \(L_1\) were previously only known to be polynomial in d. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00089-0
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Dirac proved that each n-vertex 2-connected graph with minimum degree at least k contains a cycle of length at least \(\min \{2k, n\}\) . We consider a hypergraph version of this result. A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges \(v_1,e_2,v_2, \ldots , e_c, v_1\) such that \(\{v_i,v_{i+1}\} \subseteq e_i\) for all i (with indices taken modulo c). We prove that for \(n \ge k \ge r+2 \ge 5\) , every 2-connected r-uniform n-vertex hypergraph with minimum degree at least \({k-1 \atopwithdelims ()r-1} + 1\) has a Berge cycle of length at least \(\min \{2k, n\}\) . The bound is exact for all \(k\ge r+2\ge 5\) . PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00096-1
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We show that \(\limsup E(G) / V(G) = 2.5\) over all 4-critical planar graphs G, answering a question of Grünbaum from 1988. PubDate: 2024-08-01 DOI: 10.1007/s00493-024-00100-8
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Given a graph G and a parameter r, we define the r-local matroid of G to be the matroid generated by its cycles of length at most r. Extending Whitney’s abstract planar duality theorem from 1932, we prove that for every r the r-local matroid of G is co-graphic if and only if G admits a certain type of embedding in a surface, which we call r-planar embedding. The maximum value of r such that a graph G admits an r-planar embedding is closely related to face-width, and such embeddings for this maximum value of r are quite often embeddings of minimum genus. Unlike minimum genus embeddings, these r-planar embeddings can be computed in polynomial time. This provides the first systematic and polynomially computable method to construct for every graph G a surface so that G embeds in that surface in an optimal way (phrased in our notion of r-planarity). PubDate: 2024-07-23 DOI: 10.1007/s00493-024-00118-y
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A storage code on a graph G is a set of assignments of symbols to the vertices such that every vertex can recover its value by looking at its neighbors. We consider the question of constructing large-size storage codes on triangle-free graphs constructed as coset graphs of binary linear codes. Previously it was shown that there are infinite families of binary storage codes on coset graphs with rate converging to 3/4. Here we show that codes on such graphs can attain rate asymptotically approaching 1. Equivalently, this question can be phrased as a version of hat-guessing games on graphs (e.g., Cameron et al., in: Electron J Combin 23(1):48, 2016). In this language, we construct triangle-free graphs with success probability of the players approaching one as the number of vertices tends to infinity. Furthermore, finding linear index codes of rate approaching zero is also an equivalent problem. PubDate: 2024-07-23 DOI: 10.1007/s00493-024-00114-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract For any integer \(h\geqslant 2\) , a set of integers \(B=\{b_i\}_{i\in I}\) is a \(B_h\) -set if all h-sums \(b_{i_1}+\ldots +b_{i_h}\) with \(i_1<\ldots <i_h\) are distinct. Answering a question of Alon and Erdős [2], for every \(h\geqslant 2\) we construct a set of integers X which is not a union of finitely many \(B_h\) -sets, yet any finite subset \(Y\subseteq X\) contains an \(B_h\) -set Z with \( Z \geqslant \varepsilon Y \) , where \(\varepsilon :=\varepsilon (h)\) . We also discuss questions related to a problem of Pisier about the existence of a set A with similar properties when replacing \(B_h\) -sets by the requirement that all finite sums \(\sum _{j\in J}b_j\) are distinct. PubDate: 2024-07-11 DOI: 10.1007/s00493-024-00115-1
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let G be a 3-connected ordered graph with n vertices and m edges. Let \(\textbf{p}\) be a randomly chosen mapping of these n vertices to the integer range \(\{1, 2,3, \ldots , 2^b\}\) for \(b\ge m^2\) . Let \(\ell \) be the vector of m Euclidean lengths of G’s edges under \(\textbf{p}\) . In this paper, we show that, with high probability over \(\textbf{p}\) , we can efficiently reconstruct both G and \(\textbf{p}\) from \(\ell \) . This reconstruction problem is NP-HARD in the worst case, even if both G and \(\ell \) are given. We also show that our results stand in the presence of small amounts of error in \(\ell \) , and in the real setting, with sufficiently accurate length measurements. Our method combines lattice reduction, which has previously been used to solve random subset sum problems, with an algorithm of Seymour that can efficiently reconstruct an ordered graph given an independence oracle for its matroid. PubDate: 2024-07-11 DOI: 10.1007/s00493-024-00119-x
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We show that, for any prime p and integer \(k \ge 2\) , a simple \({{\,\textrm{GF}\,}}(p)\) -representable matroid with sufficiently high rank has a rank-k flat which is either independent in M, or is a projective or affine geometry. As a corollary we obtain a Ramsey-type theorem for \({{\,\textrm{GF}\,}}(p)\) -representable matroids. For any prime p and integer \(k\ge 2\) , if we 2-colour the elements in any simple \({{\,\textrm{GF}\,}}(p)\) -representable matroid with sufficiently high rank, then there is a monochromatic flat of rank k. PubDate: 2024-07-11 DOI: 10.1007/s00493-024-00112-4
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract An amply regular graph is a regular graph such that any two adjacent vertices have \(\alpha \) common neighbors and any two vertices with distance 2 have \(\beta \) common neighbors. We prove a sharp lower bound estimate for the Lin–Lu–Yau curvature of any amply regular graph with girth 3 and \(\beta >\alpha \) . The proof involves new ideas relating discrete Ricci curvature with local matching properties: This includes a novel construction of a regular bipartite graph from the local structure and related distance estimates. As a consequence, we obtain sharp diameter and eigenvalue bounds for amply regular graphs. PubDate: 2024-07-09 DOI: 10.1007/s00493-024-00113-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A directed diameter of a directed graph is the maximum possible distance between a pair of vertices, where paths must respect edge orientations, while undirected diameter is the diameter of the undirected graph obtained by symmetrizing the edges. In 2006 Babai proved that for a connected directed Cayley graph on \( n \) vertices the directed diameter is bounded above by a polynomial in undirected diameter and \( \log n \) . Moreover, Babai conjectured that a similar bound holds for vertex-transitive graphs. We prove this conjecture of Babai, in fact, it follows from a more general bound for connected relations of homogeneous coherent configurations. The main novelty of the proof is a generalization of Ruzsa’s triangle inequality from additive combinatorics to the setting of graphs PubDate: 2024-07-09 DOI: 10.1007/s00493-024-00120-4
Hybrid journal (It can contain Open Access articles)
[2468 journals]
