Search

In this paper, we investigate representations of links that are either centrally symmetric in R3 or antipodally symmetric in S3. By using the notions of antipodally self-dual and antipodally symmetric maps, introduced and studied by the authors in [L. Montejano, J. L. Ramírez Alfonsín, and I. Rasskin, SIAM J. Discrete Math., 36 (2022), pp. 1551-1566], we are able to present sufficient combinatorial conditions for a link L to admit such representations. The latter naturally provide sufficient conditions for L to be amphichiral. We also introduce another (closely related) method yielding again sufficient conditions for L to be amphichiral. We finally prove that a link L, associated to a map G, is amphichiral if the self-dual pairing of G is not one of 6 specific cases among the classification of the 24 self-dual pairing Cor(G)⊳Aut(G). [ABSTRACT FROM AUTHOR]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]

M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687{694] that a bipartite digraph of minimum out-degree at least 3 contains two vertex disjoint directed cycles of different lengths. In this paper, we disprove this conjecture. Further, we classify strong tournaments and strong bipartite tournaments of minimum out-degree 3 without two vertex disjoint directed cycles of different lengths. [ABSTRACT FROM AUTHOR]

A graph is said to be open-neighborhood conflict-free k-colorable if there exists an assignment of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among the neighbors of v. The open-neighborhood conflict-free chromatic number χO(G) is the smallest k for which G is open-neighborhood conflict-free k-colorable. Z. Abel et al., [SIAM J. Discrete Math. 32 (2018), pp. 2675--2702] showed that χ O(G) ≤ 8 for every planar graph G and posed two open problems to ask whether χO(G) \leq 4 for every planar graph G and whether χO(G) ≤ 3 for every outerplanar graph G. We present in this paper positive answers for the above two open problems by establishing a stronger result which states that, for every integer k ≥ 2, every minor-k-colorable graph is open-neighborhood conflict-free k-colorable, where a graph G is said to be minor-k-colorable if every minor of G is k-colorable. [ABSTRACT FROM AUTHOR]

For a graph G = (V,E), a hypergraph H is called a Berge-G if there is a bijection f : E(G) → E(H) such that e ⊆ f(e) for all e ∈ E(G). The family of Berge-G hypergraphs is denoted by B(G). The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-G is denoted by exr(n, B (G)). Gyárfás [SIAM J. Discrete Math., 33 (2019), pp. 383-- 392] showed that for n ≥ 6, ex3(n, B (K4)) = [n/3] [n+1/3] [n+2/3]. However, we found an error in the proof of the result when n ≥ 7. A recent result due to Gerbner, Methuku, and Palmer [European J. Combin., 86 (2020), 103082] implies that for n ≥ 9, ex3(n, B (K4)) = [n/3] [n+1/3] [n+2/3]. In this paper we prove the remaining cases n = 7 and n = 8 for the completeness of the conclusion. [ABSTRACT FROM AUTHOR]

A cut varepsilon-sparsifier of a weighted graph G is a reweighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of varepsilon. Since their introduction by Benczur and Karger [Approximating s-t minimum cuts in O~ (n2) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC96), 1996, pp. 47-55], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIAM J. Discrete Math., 31 (2017), pp. 1263--1276] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. [ABSTRACT FROM AUTHOR]

A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and maximum degree given by Poljak and Tuza [SIAM J. Discrete Math., 7 (1994), pp. 307--313] and Johansson. There have been comparatively fewer works extending these types of bounds to graphs with a small number of triangles. One noteworthy exception is a result of Alon, Krivelevich, and Sudakov [J. Combin. Theory Ser. B, 77 (1999), pp. 73--82] bounding the chromatic number for graphs with low degree and few triangles per vertex; this bound is nearly the same as for triangle-free graphs. This type of parametrization is much less rigid and has appeared in dozens of combinatorial constructions. In this paper, we show a similar type of result for X (G) as a function of the number of vertices n, the number of edges m, as well as the triangle count (both local and global measures). Our results smoothly interpolate between the generic bounds true for all graphs and bounds for triangle-free graphs. Our results are tight for most of these cases; we show how an open problem regarding fractional chromatic number and degeneracy in triangle-free graphs can resolve the small remaining gap in our bounds. [ABSTRACT FROM AUTHOR]

This note is an erratum for the paper On the Inequalities of Projected Volumes and the Constructible Region [SIAM J. Discrete Math., 33 (2019), pp. 694--711]. There is a mistake in the proof of Theorem 4 in Section 3. However, Theorem 4 is itself correct (a proof can be found in [Inequalities on Projected Volumes, arxiv.org/abs/1909.12858, 2019] by Leader, Randelovic, and Raty), and all the other results of the paper stand. [ABSTRACT FROM AUTHOR]