Motivated by different characterizations of planar graphs and the 4-Color Theorem, several structural results concerning graphs of high chromatic number have been obtained. Toward strengthening some of these results, we consider the balanced chromatic number , χ b ( G ˆ ) , of a signed graph G ˆ . This is the minimum number of parts into which the vertices of a signed graph can be partitioned so that none of the parts induces a negative cycle. This extends the notion of the chromatic number of a graph since χ ( G ) = χ b ( G ̃ ) , where G ̃ denotes the signed graph obtained from G by replacing each edge with a pair of (parallel) positive and negative edges. We introduce a signed version of Hadwiger’s conjecture as follows. Conjecture . If a signed graph G ˆ has no negative loop and no K ̃ t -minor, then its balanced chromatic number is at most t − 1 . We prove that this conjecture is, in fact, equivalent to Hadwiger’s conjecture and show its relation to the odd Hadwiger Conjecture. Motivated by these results, we also consider the relation between subdivisions and balanced chromatic number. We prove that if ( G , σ ) has no negative loop and no K ̃ t -subdivision, then it admits a balanced 79 2 t 2 -coloring. This qualitatively generalizes a result of Kawarabayashi (2013) on totally odd subdivisions. Finally, following supportive results in the literature on the fractional variant of Hadwiger’s conjecture, we show that the fractional balanced chromatic number of any signed graph with no positive loop and no K ̃ t -minor is at most 2 t − 2 .

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on decomposing a circuit into low-depth “chunks”. This approach was however previously limited to circuits with a “layered” structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following contributions: Fractionally linear-communication MPC in the correlated randomness model. We provide an N -party protocol for computing an n -input, m -output \(\mathbb {F}\) -arithmetic circuit with s internal gates (over any basis of binary gates) with communication complexity \((\frac{2}{3}s + n + m)\cdot N\cdot \log |\mathbb {F}|\) , which can be improved to \(((1+\epsilon )\cdot \frac{2}{5}s+n+m)\cdot N\cdot \log |\mathbb {F}|\) (at the cost of increasing the computational overhead from a small constant factor to a large one). Previously, comparable protocols either used more than \(s\cdot N\cdot \log |\mathbb {F}|\) bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold. Sublinear-Communication MPC. Assuming the existence of N -party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure N -party computation for all \(\log ^{1+o(1)}\) -depth (resp. \((\log \log )^{1+o(1)}\) -depth) circuits. Previously, this result was limited to \((\mathcal {O}(\log ))\) -depth (resp. \((\mathcal {O}(\log \log ))\) -depth) circuits, or to circuits with a specific structure ( e.g. layered). The \(\boldsymbol{{N\atopwithdelims ()1}}\) -OT complexity of MPC. We introduce the “ \(N\atopwithdelims ()1\) -OT complexity of MPC ” of a function f , denoted \(C_N(f)\) , as the number of oracle calls required to securely compute f in the \(N\atopwithdelims ()1\) -OT hybrid model. We establish the following upper bound: for every \(N\ge 2\) , \(C_N(f) \le (1+g(N))\cdot \frac{2 |f|}{5}\) , where g ( N ) is an explicit vanishing function. We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.

Abstract. A circular [Formula: see text]-coloring of a signed graph [Formula: see text] is an assignment [Formula: see text] of points of a circle [Formula: see text] of circumference [Formula: see text] to the vertices of [Formula: see text] such that for each positive edge [Formula: see text] of [Formula: see text] the distance of [Formula: see text] from [Formula: see text] is at least 1 and for each negative edge [Formula: see text] the distance of [Formula: see text] from the antipode of [Formula: see text] is at least 1. The circular chromatic number of [Formula: see text], denoted [Formula: see text], is the infimum of [Formula: see text] such that [Formula: see text] admits a circular [Formula: see text]-coloring. This notion was recently defined by Naserasr, Wang, and Zhu, who, among other results, proved that for any signed [Formula: see text]-degenerate simple graph [Formula: see text] we have [Formula: see text]. For [Formula: see text], examples of signed [Formula: see text]-degenerate simple graphs of circular chromatic number [Formula: see text] are provided. But for [Formula: see text] only examples of signed 2-degenerate simple graphs of circular chromatic number arbitrarily close to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If [Formula: see text] is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then [Formula: see text]. Motivated by this observation, we provide an improved upper bound of [Formula: see text] for the circular chromatic number of a signed 2-degenerate simple graph on [Formula: see text] vertices and an improved upper bound of [Formula: see text] for the circular chromatic number of a signed bipartite planar simple graph on [Formula: see text] vertices. We then show that each of the bounds is tight for any value of [Formula: see text].

Abstract. We define the signature packing number of a signed graph [Formula: see text], denoted [Formula: see text], to be the maximum number of signatures [Formula: see text] such that each [Formula: see text] is switching-equivalent to [Formula: see text] and the sets [Formula: see text], negative edges of [Formula: see text], are pairwise disjoint. In this work, first in connection to recent developments on the theory of homomorphisms of signed graphs, we prove that for a signed graph [Formula: see text], [Formula: see text] if and only if [Formula: see text] admits a homomorphism to [Formula: see text], where [Formula: see text] is obtained from [Formula: see text] by adding a positive loop to every vertex. Noting that [Formula: see text] , signed projective cube of dimension [Formula: see text] , is the signed (Cayley) graph built on [Formula: see text] where two binary strings at Hamming distance 1 are adjacent by a positive edge and those at Hamming distance [Formula: see text] are adjacent by a negative edge. In other words, [Formula: see text] is built from the hypercube of dimension [Formula: see text] by considering all its edges as positive edges and adding a negative edge for each pair of antipodal vertices. In special cases we have the following: I. A simple graph [Formula: see text] is 4-colorable if and only if [Formula: see text]. II. A signed bipartite graph [Formula: see text] maps to [Formula: see text] if and only if [Formula: see text] noting that [Formula: see text] is the same as [Formula: see text], that is, a signed graph on [Formula: see text] where the set of negative edges forms a perfect matching. On restriction to planar graphs, I is then a restatement of the 4-color theorem, and II is implied by an unpublished work of Guenin. After further development of this theory of packing in signed graphs, we give an independent proof of II, which works on the larger class of [Formula: see text]-minor-free graphs. More precisely, we prove the following theorem. Theorem. If [Formula: see text] is a [Formula: see text] -minor-free bipartite simple graph, then for any signature [Formula: see text] we have [Formula: see text]. The statement is shown to be strictly stronger than the 4-color theorem and is proved assuming it. Furthermore, we show that I cannot be extended to the class of all signed planar simple graphs. Further developments, including algorithmic implications, are considered.

The exact distance p-power of a graph G, denoted G[#p], is a graph on vertex set V(G) in which two vertices are adjacent if they are at distance exactly p in G. Given integers k and p, we define f(k, p) to be the maximum possible order of a clique in the exact distance p-powers of graphs with maximum degree k + 1. It is easily observed that f(k, 2) ≤ k2 + k + 1. We prove that equality may only hold if a connected component of G is isomorphic to a member of the class Pk of incidence graphs of finite projective k-geometries. (These famous combinatorial structures are known to exist when k is a prime power, and are conjectured not to exist for other values of k.) We then study the case of graphs of maximum degree k + 1 with clique number k2 + k. One way to obtain such a graph is to remove a vertex from a graph in P k; we call Pk' the class of all such resulting graphs. We prove that for any graph G of maximum degree k + 1 whose exact square has a (k2 + k)-clique, either G has a subgraph isomorphic to a graph in P’k, or a connected component of G is a (k + 1)-regular bipartite graph of order 2(k2 + k). We call Ok the class of such bipartite graphs, and study their structural properties. These properties imply that (if they exist) the graphs in Ok must be highly symmetric. Using this structural information, we show that O2 contains only one graph, known as the Franklin graph. We then show that O3 also consists of a single graph, which we build. Furthermore, we show that O4 and O5 are empty. For general values of p, we prove that f(k, p) ≤ (k + 1)k[p/2] + 1, and that the bound is tight for every odd integer p ≥ 3. This implies that f(k, 2) = f(k, 3) whenever there exists a finite projective k-geometry, however, in such a case, the bound of f(k, 3) could also be reached by highly symmetric graphs built from a finite k-geometry, which is not the case for other values of k.

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang’s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of H_n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by s₀(f) s₁(f), a strictly stronger statement which implies the sensitivity conjecture.

The unit distance graph $\mathcal{R}$ is the graph with vertex set $\mathbb{R}^2$ in which two vertices (points in the plane) are adjacent if and only if they are at Euclidean distance 1. We prove that the circular chromatic number of $\mathcal{R}$ is at least 4, thus improving the known lower bound of $32/9$ obtained from the fractional chromatic number of $\mathcal{R}$.