Search

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

A remarkable conjecture of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] asserts that for any collection of n independent nonnegative, where X = Σ ni=1=i. In this paper, we investigate thisconjecture for the class of discrete log-concave probability distributions, and we prove a strengthened version. More specifically, we show that the conjectured bound 1/e holds when Xi's are independent discrete log-concave with arbitrary expectation. [ABSTRACT FROM AUTHOR]

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777--800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

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]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [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 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]

A well-studied geometric object in combinatorial optimization is the perfect matching polytope of a graph $G$---the convex hull of the incidence vectors of all perfect matchings of $G$. In any investigation concerning the perfect matching polytope, one may assume that $G$ is matching covered---that is, $G$ is a connected graph (of order at least two) and each edge of $G$ lies in some perfect matching. A graph $G$ is Birkhoff--von Neumann if its perfect matching polytope is characterized solely by nonnegativity and degree constraints. A result of Balas [North Holland Math. Stud., 59 (1981), pp. 1--13] implies that $G$ is Birkhoff--von Neumann if and only if $G$ does not contain a pair of vertex-disjoint odd cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. It follows immediately that the corresponding decision problem is in co-$\mathcal{NP}$. However, it is not known to be in $\mathcal{NP}$. The problem is in $\mathcal{P}$ if the input graph is planar---due to a result of Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324]. More recently, these authors, along with Kothari [SIAM J. Discrete Math., 32 (2018), pp. 1478--1504], have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is $\overline{C_6}$-free. The combinatorial diameter of a polytope is the diameter of its $1$-skeleton graph. A graph $G$ is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. Independent results of Balinski and Russakoff [SIAM Rev., 16 (1974), pp. 516--525] and of Chvátal [J. Combin. Theory Ser. B, 18 (1975), pp. 138--154] imply that $G$ is PM-compact if and only if $G$ does not contain a pair of vertex-disjoint even cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. Once again the corresponding decision problem is in co-$\mathcal{NP}$, but it is not known to be in $\mathcal{NP}$. The problem is in $\mathcal{P}$ if the input graph is bipartite or is near-bipartite---due to a result of Wang et al. [Discrete Math., 313 (2013), pp. 772--783]. In this paper, we consider the “intersection” of the aforementioned problems. We give an alternative description of matching covered graphs that are Birkhoff--von Neumann as well as PM-compact; our description implies that the corresponding decision problem is in $\mathcal{P}$. [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]

Let k be a positive integer. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least 2k 1 contains k vertex-disjoint cycles. This conjecture is famous as one of a hundred unsolved problems selected in [A. Bondy and M. R. Murty, Graph Theory, Springer-Verlag, London, 2008]. Lichiardopol, P\'or, and Sereni proved in [SIAM J. Discrete Math., 23 (2009), pp. 979--992] that the above conjecture holds for k = 3. Let g be the girth, i.e., the length of the shortest cycle, of a given digraph. Bang-Jensen, Bessy, and Thomass\'e conjectured in [J. Graph Theory, 75 (2014), pp. 284--302] that every digraph with girth g and minimum outdegree at least g g 1 k contains k vertex-disjoint cycles. Thomass\'e conjectured around 2006 that every oriented graph (a digraph without 2-cycles) with girth g and minimum outdegree at least h contains a path of length h(g 1), where h is a positive integer. In this paper, we first present a new shorter proof of the Bermond--Thomassen conjecture for the case of k = 3, and then we disprove the conjecture proposed by Bang-Jensen, Bessy, and Thomass\'e. Finally, we disprove the even girth case of the conjecture proposed by Thomass\'e. [ABSTRACT FROM AUTHOR]

In a seminal paper, Chen, Roughgarden, and Valiant [SIAM J. Comput., 39 (5) (2010), pp. 1799-1832] studied cost sharing protocols for network design with the objective to implement a low-cost Steiner forest as a Nash equilibrium of an induced cost-sharing game. One of the most intriguing open problems to date is to understand the power of separable cost sharing protocols in order to induce low-cost Steiner forests. In this work, we focus on undirected networks and analyze topological properties of the underlying graph so that an optimal Steiner forest can be implemented as a Nash equilibrium (by some separable cost sharing protocol) independent of the edge costs. We term a graph efficient if the above stated property holds. As our main result, we give a complete characterization of efficient undirected graphs for two-player network design games: an undirected graph is efficient if and only if it does not contain (at least) one out of few forbidden subgraphs. Our characterization implies that several graph classes are efficient: generalized series-parallel graphs, fan and wheel graphs, and graphs with small cycles. [ABSTRACT FROM AUTHOR]

In order to attack some problems in computational geometry, Hoffmann and Kriegel [SIAM J. Discrete Math., 9 (1996), pp. 210-224] considered the problem of whether a plane map can be extended to a 3-colorable triangulation by adding edges. In this paper, we improve their results to maps on nonspherical surfaces, by showing the following two results for a mosaic, that is, a map on a surface each of whose faces is triangular or quadrangular: a necessary and sufficient condition for mosaics on a surface to be extended to a 3-colorable triangulation (Theorem 5) and an explicit formula for calculating the number of distinct 3-colorable triangulations extended from a given mosaic on a surface (Theorem 6). These results suggest a significant gap between the planar case and the nonspherical case. We also show that they improve several known results and have an application to a polychromatic coloring. [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]

We consider the symmetric difference of two graphs on the same vertex set [n], which is the graph on [n] whose edge set consists of all edges that belong to exactly one of the two graphs. Let F be a class of graphs, and let MF(n) denote the maximum possible cardinality of a family G of graphs on [n] such that the symmetric difference of any two members in G belongs to F. These concepts have been recently investigated by Alon et al. [SIAM J. Discrete Math., 37 (2023), pp. 379-403] with the aim of providing a new graphic approach to coding theory. In particular, MF(n) denotes the maximum possible size of this code. Existing results show that as the graph class F changes, MF(n) can vary from n to 2(1+0(1))(2n). We study several phase transition problems related to MF(n) in general settings and present a partial solution to a recent problem posed by Alon et al. [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]

For integers k ≥1 and m ≥2, let g(k,m) be the least integer n ≥1 such that every graph with chromatic number at least n contains a (k + 1)-connected subgraph with chromatic number at least m. Refining the recent result of Gir\~ao and Narayanan [Bull. Lond. Math. Soc., 54 (2022), pp. 868--875] that g(k 1, k) ≤ 7k + 1 for all k≥ 2, we prove that g(k,m) ≤ max(m + 2k 2, (3 + 1/16)k≤) for all k ≥ 1 and m≥2. This sharpens earlier results of Alon et al. [J. Graph Theory, 11 (1987), pp. 367-371], of Chudnovsky [J. Combin. Theory Ser. B, 103 (2013), pp. 567-586], and of Penev, Thomass'e, and Trotignon [SIAM J. Discrete Math., 30 (2016), pp. 592--619]. Our result implies that g(k, k + 1) (3 + 1/16)k for all k \geq 1, making a step closer towards a conjecture of Thomassen [J. Graph Theory, 7 (1983), pp. 261--271] that g(k, k +1)≤3k +1, which was originally a result with a false proof and was the starting point of this research area. [ABSTRACT FROM AUTHOR]

For every fixed k ≥ 4, it is proved that if an n-vertex directed graph has at most t pairwise arc-disjoint directed k-cycles, then there exists a set of at most 2/3 kt + o(n²) arcs that meets all directed k-cycles and that the set of k-cycles admits a fractional cover of value at most 2/3 kt. It is also proved that the ratio 2/3 k cannot be improved to a constant smaller than k/2 2. Fork = 5 the constant 2k/3 is improved to 25/8 and for k = 3 it was recently shown by Cooper et al. [European J. Combin., 101 (2022), 103462] that the constant can be taken to be 9/5. The result implies a deterministic polynomial time 2/3k-approximation algorithm for the directed k-cycle cover problem, improving upon a previous (k 1)-approximation algorithm of Kortsarz, Langberg, and Nutov, [SIAM J. Discrete Math., 24 (2010), pp. 255--269]. More generally, for every directed graph H we introduce a graph parameter f(H) for which it is proved that if an n-vertex directed graph has at most t pairwise arc-disjoint H-copies, then there exists a set of at most f(H)t + o(n²) arcs that meets all H-copies and that the set of H-copies admits a fractional cover of value at most f(H)t. It is shown that for almost all H it holds that f(H) \approx | E(H)|/2 and that for every k-vertex tournament H it holds that f(H) ≤ k²/4). [ABSTRACT FROM AUTHOR]

Given an undirected n-vertex graph and k pairs (si,ti),..,, (sfc,tfc) of terminal vertices, the fc-DlSJOINT SHORTEST PATHS (fc-SDP) problem asks whether there are k pairwise vertex-disjoint paths Pi,...,Pk such that Pi is a shortest s-ti-path for each i E [fc]. Recently, Lochet [Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA '21), SIAM, 2021, pp. 169-178] provided an algorithm that solves fc-SDP in no time, answering a 20-year old question about the computational complexity of fc-SDP for constant fc. On the one hand, we present an improved no-time algorithm based on a novel geometric view on this problem. For the special case fc = 2 on m-edge graphs, we show that the running time can be further reduced to O(nm) by small modifications of the algorithm and a refined analysis. On the other hand, we show that fc-SDP is W[l]-hard with respect to fc, showing that the dependency of the degree of the polynomial running time on the parameter fc is presumably unavoidable. [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]

We show that for pairs (Q, R) and (S, T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V (G) - (Q \cup R \cup S \cup T) such that there are two ways to reduce G by a vertex-minor operation that removes v while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (SIAM J. Discrete Math., 28 (2014), pp. 1402--1404) for matroids restricted to binary matroids. [ABSTRACT FROM AUTHOR]

Consider a rooted tree T with leaf-set [n] and with all nonleaf vertices having out-degree 2, at least. A rooted tree T with leaf-set S⊂[n] is induced by S in T if T is the lowest common ancestor subtree for S, with all its degree-2 vertices suppressed. A "maximum agreement subtree" (MAST) for a pair of two trees T′ and T′′ is a tree T with a largest leaf-set S⊂[n] such that T is induced by S both in T′ and T′′. Bryant, McKenzie, and Steel [BioConsensus, AMS, Providence, RI, 2003, pp. 55-65] and Bernstein et al. [SIAM J. Discrete Math., 29 (2015), pp. 2065-2074] proved, among other results, that for T′ and T′′ being two independent copies of a random binary (uniform or Yule-Harding distributed) tree T, the likely magnitude order of MAST(T′,T′′) is O(n1/2). We prove this bound for a wide class of random rooted trees: T is a terminal tree of a branching, Galton-Watson, process with an ordered-offspring distribution of mean 1, conditioned on "total number of leaves is n." [ABSTRACT FROM AUTHOR]

A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number c such that G is c-closed. Fox et al. [SIAM J. Comput., 49 (2020), pp. 448-464] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size kO(c), that Induced Matching admits a kernel with O(c7k8) vertices, and that Irredundant Set admits a kernel with O(c5/2k3) vertices. As we show, our kernelizations exploit the fact that c-closed graphs have polynomially bounded Ramsey numbers. [ABSTRACT FROM AUTHOR]

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s \geq 1, both problems are polynomial-time solvable for sP3-free graphs and (sP1 + P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1 + P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., Theoret. Comput. Sci., 705 (2018), pp. 75--83], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica, 82 (2020), pp. 2841--2866] and P5-free graphs [Abrishami et al., Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 1948--1964]. Together, the new results also show that both problems exhibit the same behavior on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1 + P5)-free graph G a largest induced subgraph whose blocks belong to some finite class \scrC of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs. [ABSTRACT FROM AUTHOR]

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a "branch-decomposition" of these subspaces of width at most k that is a subcubic tree T with n leaves mapped bijectively to the subspaces such that for every edge e of T, the sum of subspaces associated to the leaves in one component of T -e and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most k. This problem includes the problems of computing branch-width of F-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. Our algorithm is analogous to the algorithm of Bodlaender and Kloks [J. Algorithms, 21 (1996), pp. 358-402] on tree-width of graphs. To extend their framework to branchdecompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. The only known previous fixed-parameter algorithm for branch-width of F-represented matroids was due to Hliněný and Oum [SIAM J. Comput., 38 (2008), pp. 1012-1032] that runs in time O(n3) where n is the number of elements of the input F-represented matroid. But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. [J. Combin. Theory Ser. B, 88 (2003), pp. 261-265] that the number of forbidden minors is finite and uses the algorithm of Hliněný [J. Combin. Theory Ser. B, 96 (2006), pp. 325-351] on checking monadic second-order formulas on F-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed k. [ABSTRACT FROM AUTHOR]

We prove several versions of Alon's necklace-splitting theorem, subject to additional constraints, as illustrated by the following results. (1) The "almost equicardinal necklace-splitting theorem"" claims that, without increasing the number of cuts, one guarantees the existence of a fair splitting such that each thief is allocated almost the same number of pieces of the necklace (including "degenerate pieces"" if they exist), provided the number of thieves r = pnu is a prime power. By "almost the same"" we mean that for each pair of thieves one of them can be given at most one piece more (one piece less) than the other. (2) The "binary splitting theorem"" claims that if r = 2d and the thieves are associated with the vertices of a d-cube, then, without increasing the number of cuts, one can guarantee the existence of a fair splitting such that adjacent pieces are allocated to thieves that share an edge of the cube. This result provides a positive answer to the "binary splitting necklace conjecture"" in the case r = 2d from Conjecture 2.11 in [M. Asada et al., SIAM J. Discrete Math., 32 (2018), pp. 591--610]. (3) An interesting variation arises when the thieves have their own individual preferences. We prove several envy-free, fair necklace-splitting theorems of various level of generality, as illustrated by the envy-free versions of (a) Alon's original necklace-splitting theorem, (b) the almost equicardinal splitting theorem, and (c) the binary splitting theorem, etc. [ABSTRACT FROM AUTHOR]

We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [Kushilevitz, Ostrovsky, and Ros'en, J. Comput. Syst. Sci., 58 (1999), pp. 129--136] and [G'al and Ros'en, SIAM J. Comput., 31 (2002), pp. 1424--1437]. More concretely, we consider the randomness complexity of the basic Boolean function and, that serves as a building block in the design of many private protocols. We show that and cannot be privately computed using a single random bit, thus giving the first nontrivial lower bound on the 1-private randomness complexity of an explicit Boolean function, f: { 0, 1} n rightarrow { 0, 1}. We further show that and, on any number of inputs n (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of n = 3 players), improving the upper bound of 73 random bits implicit in [Kushilevitz, Ostrovsky, and Ros'en, J. Comput. Syst. Sci., 58 (1999), pp. 129--136]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for xor, which is 1-random, and for several degenerate functions). [ABSTRACT FROM AUTHOR]

We show that the expected size of the maximum agreement subtree of two n-leaf trees, uniformly random among all trees with the shape, is\Theta (\surd n). To derive the lower bound, we prove a global structural result on a decomposition of rooted binary trees into subgroups of leaves called blobs. To obtain the upper bound, we generalize a first moment argument from [D. I. Bernstein, et al., SIAM J. Discrete Math., 29 (2015), pp. 2065--2074] for random tree distributions that are exchangeable and not necessarily sampling consistent. [ABSTRACT FROM AUTHOR]

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]

A function f: f0; 1gn! f0; 1g is said to be k-monotone if it flips between 0 and 1 at most k times on every ascending chain. Such functions represent a natural generalization of (1-)monotone functions, and have been recently studied in circuit complexity, PAC learning, and cryptography. Our work is part of a renewed focus in understanding testability of properties characterized by freeness of arbitrary order patterns as a generalization of monotonicity. Recently, Canonne et al. [Innovations in Theoretical Computer Science, Schloss-Dagstuhl{Leibniz-Zentrum für Informatik GmBH, Wadern, Germany, 2017, 29] initiate the study of k-monotone functions in the area of property testing, and Newman et al. [SODA, SIAM, Philadelphia, 2017, pp. 1582{1597] study testability of families characterized by freeness from order patterns on real-valued functions over the line [n] domain. We study k-monotone functions in the more relaxed parametrized property testing model, introduced by Parnas, Ron, and Rubinfeld [J. Comput. System Sci., 72 (2006), pp. 1012{1042]. In this process we show strong lower bounds on testing k-monotonicity. Specifically, we show that testing 2-monotonicity on the hypercube nonadaptively with one-sided error requires an exponential in p n number of queries. This behavior shows a stark contrast with testing (1-)monotonicity, which only needs ~O -p n = queries. Furthermore, even the apparently easier task of distinguishing 2-monotone functions from functions that are far from being n:01-monotone also requires an exponential number of queries. [ABSTRACT FROM AUTHOR]

Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented a proof of a theorem of Reed and Wakabayashi that a brick G is nonsolid if and only if there exist two vertex-disjoint odd cycles C1 and C2 such that G V (C1 ∪ C2) has a perfect matching. Consequently, every brick with no two vertex-disjoint odd cycles is solid. Recently, Lucchesi et al. [SIAM J. Discrete Math., 32 (2018), pp. 1478--1501] constructed infinite families of solid bricks containing two vertex-disjoint odd cycles. Noticing that none of these graphs is cubic, they conjectured that no cubic solid brick contains two vertex-disjoint odd cycles. In this note, we present an infinite family of graphs showing that this conjecture fails. We further show that the minimum counterexample is unique, which has 12 vertices. [ABSTRACT FROM AUTHOR]