Denote by $K_p(n,k)$ the random subgraph of the usual Kneser graph $K(n,k)$ in which edges appear independently, each with probability $p$. Answering a question of Bollobás, Narayanan, and Raigorodskii, we show that there is a fixed $p<1$ such that a.s. (i.e., with probability tending to 1 as $k\rightarrow\infty$) the maximum independent sets of $K_p(2k+1, k)$ are precisely the sets $\{A\in V(K(2k+1,k)): x\in A\}$ ($x\in [2k+1]$). We also complete the determination of the order of magnitude of the “threshold" for the above property for general $k$ and $n\geq 2k+2$. This is new for $k\sim n/2$, while for smaller $k $ it is a recent result of Das and Tran.

We show that for all sufficiently large $d$, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on ${\mathbb Z}^d$ admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in ${\mathbb Z}^d$, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex $v$ in the box, then the probability that $v$ gets color 0 is exponentially small in $d$. The proof proceeds through an analysis of a certain type of cutset separating $v$ from the boundary of the box and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on ${\mathbb Z}^d$. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus ${\mathbb Z}^d_n$. We show that there is a constant $\rho \approx 0.22$ such that for all even $n \geq 4$ and $d$ sufficiently large, if ${\mathcal M}$ is a Markov chain on the set of proper 3-colorings of ${\mathbb Z}^d_n$ that updates the color of at most $\rho n^d$ vertices at each step and whose stationary distribution is uniform, then the mixing time of ${\mathcal M}$ (the time taken for ${\mathcal M}$ to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in $n^{d-1}$.

We prove a dual version of the celebrated inequality of D. Reimer (a.k.a. the van den Berg-Kesten conjecture). We use the dual inequality to prove a combinatorial conjecture of S. Rudich motivated by questions in cryptographic complexity. One consequence of Rudich's Conjecture is that there is an oracle relative to which one-way functions exist but one-way permutations do not. The dual inequality has another combinatorial consequence which allows R. Impagliazzo and S. Rudich to prove that if P=NP then NP/spl cap/coNP/spl sube/i.o.AvgP relative to a random oracle.

We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M/2

We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks.

Article Free Access Share on On the second eigenvalue of random regular graphs Authors: J. Friedman Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile , J. Kahn Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJ Dept. of Mathematics and Center for O. R., Rutgers University, New Brunswick, NJView Profile , E. Szemerédi Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of Sciences Dept. of Computer Science, Rutgers University, New Brunswick, NJ and Mathematical Institute of the Hungarian Academy of SciencesView Profile Authors Info & Claims STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computingFebruary 1989 Pages 587–598https://doi.org/10.1145/73007.73063Published:01 February 1989Publication History 104citation2,261DownloadsMetricsTotal Citations104Total Downloads2,261Last 12 Months122Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Misère End Play is a two-person constant sum game with perfect information. The game uses a deck of cards that consists of a single totally ordered suit of $2n$ cards. To begin play, the deck is divided into two hands of n cards each, held by players Left and Right, with one player designated as having the lead. The player on lead plays one of his cards, and the other player, after seeing it, plays one of his cards. The player with the higher card wins a “trick” and obtains the lead. The cards in the trick are removed and play continues until all cards are played. In Misère End Play each player's goal is to take as few tricks as possible. Misère End Play is shown to have a simple optimal strategy.

Methods from harmonic analysis are used to prove some general theorems on Boolean functions. These connections with harmonic analysis viewed by the authors are very promising; besides the results on Boolean functions they enable them to prove theorems on the rapid mixing of the random walk on the cube and in the extremal theory of finite sets.>

We show that any finite partially ordered set P contains a pair of elements x and y such that the proportion of linear extensions of P in which x lies below y is between 3/11 and 8/11. A consequence is that the information-theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: if X is a totally ordered set about which we are given some partial information, and if e(X) is the number of total orderings of X compatible with this partial information, then it is possible to sort X using no more than c log2e(X) comparisons ([email protected]@@@2.17).

The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the digraph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity θ(v2) where v is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper it is shown that Karp's conjecture follows from another conjecture concerning group actions on topological spaces. A special case of this conjecture is proved and applied to prove Karp's conjecture for the case of properties of graph and digraph properties on a prime power number of vertices.