By a theorem of Johansson, every triangle-free graph $G$ of maximum degree $\Delta$ has chromatic number at most $(C+o(1))\Delta/\log \Delta$ for some universal constant $C > 0$. Using the entropy compression method, Molloy proved that one can in fact take $C = 1$. Here we show that for every $q \geq (1 + o(1))\Delta/\log \Delta$, the number $c(G,q)$ of proper $q$-colorings of $G$ satisfies $c(G, q) \,\geq\, \left(1 - \frac{1}{q}\right)^m ((1-o(1))q)^n$, where $n = |V(G)|$ and $m = |E(G)|$. Except for the $o(1)$ term, this lower bound is best possible as witnessed by random $\Delta$-regular graphs. When $q = (1 + o(1)) \Delta/\log \Delta$, our result yields the inequality $c(G,q) \,\geq\, \exp\left((1 - o(1)) \frac{\log \Delta}{2} n\right)$, which implies the optimal lower bound on the number of independent sets in $G$ due to Davies, Jenssen, Perkins, and Roberts. An important ingredient in our proof is the counting method that was recently developed by Rosenfeld. As a byproduct, we obtain an alternative proof of Molloy's bound $\chi(G) \leq (1 + o(1))\Delta/\log \Delta$ using Rosenfeld's method in place of entropy compression.
相關內容
For a matrix $A\in \mathbb{R}^{n\times d}$ with $n\geq d$, we consider the dual problems of $\min \|Ax-b\|_p^p, \, b\in \mathbb{R}^n$ and $\min_{A^\top x=b} \|x\|_p^p,\, b\in \mathbb{R}^d$. We improve the runtimes for solving these problems to high accuracy for every $p>1$ for sufficiently sparse matrices. We show that recent progress on fast sparse linear solvers can be leveraged to obtain faster than matrix-multiplication algorithms for any $p > 1$, i.e., in time $\tilde{O}(pn^\theta)$ for some $\theta < \omega$, the matrix multiplication constant. We give the first high-accuracy input sparsity $p$-norm regression algorithm for solving $\min \|Ax-b\|_p^p$ with $1 < p \leq 2$, via a new row sampling theorem for the smoothed $p$-norm function. This algorithm runs in time $\tilde{O}(\text{nnz}(A) + d^4)$ for any $1<p\leq 2$, and in time $\tilde{O}(\text{nnz}(A) + d^\theta)$ for $p$ close to $2$, improving on the previous best bound where the exponent of $d$ grows with $\max\{p, p/(p-1)\}$.
In this paper, we propose a new method for offline change-point detection on some parameters of the distribution of a random vector. We introduce a penalized maximum likelihood approach that can be efficiently computed by a dynamic programming algorithm or approximated by a fast greedy binary splitting algorithm. We prove both algorithms converge almost surely to the set of change-points under very general assumptions on the distribution and independent sampling of the random vector. In particular, we show the assumptions leading to the consistency of the algorithms are satisfied by categorical and Gaussian random variables. This new approach is motivated by the problem of identifying homozygosity islands on the genome of individuals in a population. Our method directly tackles the issue of identification of the homozygosity islands at the population level, without the need of analyzing single individuals and then combining the results, as is made nowadays in state-of-the-art approaches.
A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports evaluating functions on shared secrets by means of a local mapping from input shares to output shares. We initiate the study of the download rate of HSS, namely, the achievable ratio between the length of the output shares and the output length when amortized over $\ell$ function evaluations. We obtain the following results. * In the case of linear information-theoretic HSS schemes for degree-$d$ multivariate polynomials, we characterize the optimal download rate in terms of the optimal minimal distance of a linear code with related parameters. We further show that for sufficiently large $\ell$ (polynomial in all problem parameters), the optimal rate can be realized using Shamir's scheme, even with secrets over $\mathbb{F}_2$. * We present a general rate-amplification technique for HSS that improves the download rate at the cost of requiring more shares. As a corollary, we get high-rate variants of computationally secure HSS schemes and efficient private information retrieval protocols from the literature. * We show that, in some cases, one can beat the best download rate of linear HSS by allowing nonlinear output reconstruction and $2^{-\Omega(\ell)}$ error probability.
This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph $G$ and an arbitrary set of $k$ terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k\}\}$ that are required to be connected. The goal is to maintain a minimum-weight sub-graph that satisfies all the connectivity requirements as the pairs are revealed one by one. It has been known for a long time that no algorithm (even randomized) can be better than $\Omega(\log(k))$-competitive for this problem. Interestingly, a simple greedy algorithm is already very efficient for this problem. This algorithm can be informally described as follows: Upon arrival of a new pair $\{s_i,t_i\}$, connect $s_i$ and $t_i$ with the shortest path in the current metric, contract the metric along the chosen path and wait for the next pair. Although simple and intuitive, greedy proved itself challenging to analyze and its competitive ratio is a long-standing open problem in the area of online algorithms. The last progress on this question is due to an elegant analysis by Awerbuch, Azar, and Bartal [SODA~1996], who showed that greedy is $O(\log^2(k))$-competitive. Our main result is to show that greedy is in fact $O(\log(k)\log\log(k))$-competitive on a wide class of instances. In particular, this wide class of instances contains all the instances that were exhibited in the literature until now.
We introduce the following variant of the VC-dimension. Given $S \subseteq \{0, 1\}^n$ and a positive integer $d$, we define $\mathbb{U}_d(S)$ to be the size of the largest subset $I \subseteq [n]$ such that the projection of $S$ on every subset of $I$ of size $d$ is the $d$-dimensional cube. We show that determining the largest cardinality of a set with a given $\mathbb{U}_d$ dimension is equivalent to a Tur\'an-type problem related to the total number of cliques in a $d$-uniform hypergraph. This allows us to beat the Sauer--Shelah lemma for this notion of dimension. We use this to obtain several results on $\Sigma_3^k$-circuits, i.e., depth-$3$ circuits with top gate OR and bottom fan-in at most $k$: * Tight relationship between the number of satisfying assignments of a $2$-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. '00). * Improved $\Sigma_3^3$-circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement. * We make progress towards settling the $\Sigma_3^2$ complexity of the inner product function and all degree-$2$ polynomials over $\mathbb{F}_2$ in general. The question of determining the $\Sigma_3^3$ complexity of IP was recently posed by Golovnev, Kulikov, and Williams (ITCS'21).
Let $D$ be a digraph and let $\lambda(D)$ denote the number of vertices in a longest path of $D$. For a pair of vertex-disjoint induced subdigraphs $A$ and $B$ of $D$, we say that $(A,B)$ is a partition of $D$ if $V(A)\cup V(B)=V(D).$ The Path Partition Conjecture (PPC) states that for every digraph, $D$, and every integer $q$ with $1\leq q\leq\lambda(D)-1$, there exists a partition $(A,B)$ of $D$ such that $\lambda(A)\leq q$ and $\lambda(B)\leq\lambda(D)-q.$ Let $T$ be a digraph with vertex set $\{u_1,\dots, u_t\}$ and for every $i\in [t]$, let $H_i$ be a digraph with vertex set $\{u_{i,j_i}\colon\, j_i\in [n_i]\}$. The {\em composition} $Q=T[H_1,\dots , H_t]$ of $T$ and $H_1,\ldots, H_t$ is a digraph with vertex set $\{u_{i,j_i}\colon\, i\in [t], j_i\in [n_i]\}$ and arc set $$A(Q)=\cup^t_{i=1}A(H_i)\cup \{u_{i,j_i}u_{p,q_p}\colon\, u_iu_p\in A(T), j_i\in [n_i], q_p\in [n_p]\}.$$ We say that $Q$ is acyclic {(semicomplete, respectively)} if $T$ is acyclic {(semicomplete, respectively)}. In this paper, we introduce a conjecture stronger than PPC using a property first studied by Bang-Jensen, Nielsen and Yeo (2006) and show that the stronger conjecture holds for wide families of acyclic and semicomplete compositions.
Let $G$ be a graph with vertex set $V$. Two disjoint sets $V_1, V_2 \subseteq V$ form a coalition in $G$ if none of them is a dominating set of $G$ but their union $V_1\cup V_2$ is. A vertex partition $\Psi=\{V_1,\ldots, V_k\}$ of $V$ is called a coalition partition of $G$ if every set $V_i\in \Psi$ is either a dominating set of $G$ with the cardinality $|V_i|=1$, or is not a dominating set but for some $V_j\in \Psi$, $V_i$ and $V_j$ form a coalition. The maximum cardinality of a coalition partition of $G$ is called the coalition number of $G$, denoted by $\mathcal{C}(G)$. A $\mathcal{C}(G)$-partition is a coalition partition of $G$ with cardinality $\mathcal{C}(G)$. Given a coalition partition $\Psi=\{V_1, V_2,\ldots, V_r\}$ of $G$, a coalition graph $CG(G, \Psi)$ is associated on $\Psi$ such that there is a one-to-one correspondence between its vertices and the members of $\Psi$. Two vertices of $CG(G, \Psi)$ are adjacent if and only if the corresponding sets form a coalition in $G$. In this paper, we first show that for any graph $G$ with $\delta(G)=1$, $\mathcal{C}(G)\leq 2\Delta(G)+2$, where $\delta(G)$ and $\Delta(G)$ are the minimum degree and the maximum degree of $G$, respectively. Moreover, we characterize all graphs $G$ with $\delta(G)\leq 1$ and $\mathcal{C}(G)=n$, where $n$ is the number of vertices of $G$. Furthermore, we characterize all trees $T$ with $\mathcal{C}(T)=n$ and all trees $T$ with $\mathcal{C}(T)=n-1$. This solves partially one of the open problem posed in \cite{coal0}. On the other hand, we theoretically and empirically determine the number of coalition graphs that can be defined by all coalition partitions of a given path $P_k$. Furthermore, we show that there is no universal coalition path, a path whose coalition partitions defines all possible coalition graphs. These solve two open problems posed by Haynes et al. \cite{coal1}.
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems. In the average case setting, SoS lower bounds provide strong evidence of algorithmic hardness or information-computation gaps. Prior to this work, SoS lower bounds have been obtained for problems in the "dense" input regime, where the input is a collection of independent Rademacher or Gaussian random variables, while the sparse regime has remained out of reach. We make the first progress in this direction by obtaining strong SoS lower bounds for the problem of Independent Set on sparse random graphs. We prove that with high probability over an Erdos-Renyi random graph $G\sim G_{n,\frac{d}{n}}$ with average degree $d>\log^2 n$, degree-$D_{SoS}$ SoS fails to refute the existence of an independent set of size $k = \Omega\left(\frac{n}{\sqrt{d}(\log n)(D_{SoS})^{c_0}} \right)$ in $G$ (where $c_0$ is an absolute constant), whereas the true size of the largest independent set in $G$ is $O\left(\frac{n\log d}{d}\right)$. Our proof involves several significant extensions of the techniques used for proving SoS lower bounds in the dense setting. Previous lower bounds are based on the pseudo-calibration heuristic of Barak et al [FOCS 2016] which produces a candidate SoS solution using a planted distribution indistinguishable from the input distribution via low-degree tests. In the sparse case the natural planted distribution does admit low-degree distinguishers, and we show how to adapt the pseudo-calibration heuristic to overcome this. Another notorious technical challenge for the sparse regime is the quest for matrix norm bounds. In this paper, we obtain new norm bounds for graph matrices in the sparse setting.
We consider the algorithmic complexity of recognizing bipartite temporal graphs. Rather than defining these graphs solely by their underlying graph or individual layers, we define a bipartite temporal graph as one in which every layer can be 2-colored in a way that results in few changes between any two consecutive layers. This approach follows the framework of multistage problems that has received a growing amount of attention in recent years. We investigate the complexity of recognizing these graphs. We show that this problem is NP-hard even if there are only two layers or if only one change is allowed between consecutive layers. We consider the parameterized complexity of the problem with respect to several structural graph parameters, which we transfer from the static to the temporal setting in three different ways. Finally, we consider a version of the problem in which we only restrict the total number of changes throughout the lifetime of the graph. We show that this variant is fixed-parameter tractable with respect to the number of changes.
We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tilde O(n\cdot \max(m^{2/3}, n))$ time. This improves on the 30 year old bound of $\tilde O(nm)$ obtained by Hao and Orlin for this problem. Our main technique is to reduce the directed mincut problem to $\tilde O(\min(n/m^{1/3}, \sqrt{n}))$ calls of {\em any} maxflow subroutine. Using state-of-the-art maxflow algorithms, this yields the above running time. Our techniques also yield fast {\em approximation} algorithms for finding minimum cuts in directed graphs. For both edge and vertex weighted graphs, we give $(1+\epsilon)$-approximation algorithms that run in $\tilde O(n^2 / \epsilon^2)$ time.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191