Is every polygonal room in the plane illuminable from some point
v1.3 research notesStraus: Is every polygonal room in the plane illuminable from some point? See this....
Is it true that every graph whose vertices have odd degree greater than one contains a cycle of length 2^(n) for some n
v1.3 research notesErdős-Gyárfás: Is it true that every graph whose vertices have odd degree greater than one contains a cycle of length 2^(n) for some n? This one has k...
Show that the discrepancy of any hypergraph H is at most c|E(H)|^(1/2)
v1.3 research notesBeck: Show that the discrepancy of any hypergraph H is at most c|E(H)|^(1/2)...
Does lim R(k,k)^(1/k) exist
v1.3 research notesErdős: Does lim R(k,k)^(1/k) exist? What is it? (If it exists, it's between sqrt(2) and 4.) See "Small Ramsey Numbers" by Stanislaw Radziszowski....
Suppose G has n vertices and no induced copy of H
v1.3 research notesErdős, Hajnal: Suppose G has n vertices and no induced copy of H. Is there an ľ > 0, depending only on H, so that the homogeneous number of G (i.e., t...
Define the "crossing number" of a graph to be the minimum number of (topological) crossings of edges in any straight-lin
v1.3 research notesPach, Tóth: Define the "crossing number" of a graph to be the minimum number of (topological) crossings of edges in any straight-line embedding in the...
Define the discrepancy of a graph to be the largest value of D(S,T) = | |S||T|/2 - e(S,T) |, over all disjoint vertex se
v1.3 research notesChung, Graham: Define the discrepancy of a graph to be the largest value of D(S,T) = | |S||T|/2 - e(S,T) |, over all disjoint vertex sets S and T. Sup...
Show that every (1/2+ľ)|E(ő_(n))| edges of the n-cube ő_(n) contains a C_(4) when n is sufficiently large
v1.3 research notesErdős: Show that every (1/2+ľ)|E(ő_(n))| edges of the n-cube ő_(n) contains a C_(4) when n is sufficiently large. (The best known value of ľ is around...
The "cycle double cover conjecture" states that every bridgeless graph contains a set of cycles which cover each edge of
v1.3 research notesSeymour/Szekeres: The "cycle double cover conjecture" states that every bridgeless graph contains a set of cycles which cover each edge of the graph e...
"Seymour's Second Neighborhood Conjecture" Any oriented graph has a vertex whose outdegree is at most its second outdegr
v1.3 research notesSeymour: "Seymour's Second Neighborhood Conjecture" Any oriented graph has a vertex whose outdegree is at most its second outdegree (vertices at direc...
Suppose that G is a tree
v1.3 research notesGraham: Suppose that G is a tree. Denote by L(G) the line graph of G. Is the sequence |G|, |L(G)|, |L(L(G))|, |L(L(L(G)))| ... unique to G? That is, c...
What is the list-chromatic number of Sudoku
v1.3 research notes: What is the list-chromatic number of Sudoku? That is, suppose one places k symbols (aka colors) in each cell of a Sudoku board -- not necessarily al...
A graph G is said to be uniquely H-saturated if it contains no H, but adding any edge to G creates exactly one copy of H
v1.3 research notes: A graph G is said to be uniquely H-saturated if it contains no H, but adding any edge to G creates exactly one copy of H (up to isomorphism). Clearl...
A graph G is said to be uniquely colorable it has only one optimal coloring up to permutation of the colors
v1.3 research notes: A graph G is said to be uniquely colorable it has only one optimal coloring up to permutation of the colors. (That is, there is only one partition i...
What is the meaning of the multiplicity of zero as a root of a hypergraph's (or graph's) characteristic polynomial
v1.3 research notesNikiforov: What is the meaning of the multiplicity of zero as a root of a hypergraph's (or graph's) characteristic polynomial?...
What are the (homogeneous adjacency) spectra of the ultracube and the complete hypergraph
v1.3 research notes/Dutle : What are the (homogeneous adjacency) spectra of the ultracube and the complete hypergraph? (Ultracube = cartesian power of a hyperedge.)...
What is the (homogeneous adjacency) spectrum of the Fano plane
v1.3 research notes/Clark : What is the (homogeneous adjacency) spectrum of the Fano plane?...
Is it true that the sum of the k largest Laplacian eigenvalues of a graph with m edges is at most k(k+1)/2+m
v1.3 research notesBrouwer : Is it true that the sum of the k largest Laplacian eigenvalues of a graph with m edges is at most k(k+1)/2+m?...
Given a permutation σ, what is the maximum number of copies of σ that a permutation on n symbols may contain
v1.3 research notesGiven a permutation σ, what is the maximum number of copies of σ that a permutation on n symbols may contain?...
Given two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random f
v1.3 research notes: Given two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random from those permutations on n ...
Is it possible for a permutation on n symbols to contain exactly n
v1.3 research notes: Is it possible for a permutation on n symbols to contain exactly n!/(m!^(2)(n - m)!) copies of each permutation on m symbols? (Yes for m=1,2,3. Unkn...
Show that the inversion permutation, i
v1.3 research notesPropp: Show that the inversion permutation, i.e., the one which takes s to 1/s mod p, has longest increasing subsequence of length 2√ p(1+o(1)), i.e.,...
What is the length of the shortest sequence in [n]* containing, as a (consecutive) subword, each permutation of [n]
v1.3 research notesWhat is the length of the shortest sequence in [n]* containing, as a (consecutive) subword, each permutation of [n]? See this, this, this, this, and t...
A d-dimensional permutation of order n is an n-by-n-by
v1.3 research notesLinal/Luria: A d-dimensional permutation of order n is an n-by-n-by-...-by-n (d+1)-dimensional array of zeroes and ones, with the property that every ...
What are the Whitney numbers of the (lattice of contractions of the) n-cube
v1.3 research notes: What are the Whitney numbers of the (lattice of contractions of the) n-cube? What if contractions equivalent under symmetries of the cube are identi...
Is the weak order on S_(n) (the "inversion" poset) Sperner
v1.3 research notesIs the weak order on S_(n) (the "inversion" poset) Sperner?...
Is the poset of integer partitions ordered by refinement Sperner
v1.3 research notesIs the poset of integer partitions ordered by refinement Sperner?...
How many comparisons are needed to determine a linear order of the Boolean poset
v1.3 research notesFishburn, Pekec, Reeds: How many comparisons are needed to determine a linear order of the Boolean poset? That is, what is the fewest number of questi...
Show that the jump number of a random linear extension of a grid poset (i
v1.3 research notes: Show that the jump number of a random linear extension of a grid poset (i.e., a product of chains) is close to the maximum w.h.p. (For the "symmetri...
("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_
v1.3 research notesGriggs, Lu: ("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_(2) as a subposet?...
For any poset P, define ex(n,P) to be the size of the largest subset of the Boolean lattice B_(n) which includes no (inj
v1.3 research notesGriggs, Lu: For any poset P, define ex(n,P) to be the size of the largest subset of the Boolean lattice B_(n) which includes no (injective) copy of P ...
"1/3 - 2/3 Conjecture" For every poset that is not a chain, there is some pair of elements x and y so that x appears abo
v1.3 research notesKislitsyn: "1/3 - 2/3 Conjecture" For every poset that is not a chain, there is some pair of elements x and y so that x appears above y in a random li...
Is enumeration of pressing sequences of bicolored graphs (aka simple pseudographs) #P-hard
v1.3 research notes: Is enumeration of pressing sequences of bicolored graphs (aka simple pseudographs) #P-hard? Is there an FPRAS for sampling them?...
Is the 1/3-2/3 Conjecture for Pressing Sequences true
v1.3 research notes: Is the 1/3-2/3 Conjecture for Pressing Sequences true? That is, if a graph G is not uniquely pressable, is it true that there much be two vertices x...
A covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one of the codewo
v1.3 research notesA covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one of the codewords by changing at most R bits...
An asymmetric covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one o
v1.3 research notes/Ellis/Kahng: An asymmetric covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one of the codewords ...
An asymmetric packing code of radius R is a set of binary n-words so that no binary n-word can be reached from more than
v1.3 research notes/Ellis/Kahng: An asymmetric packing code of radius R is a set of binary n-words so that no binary n-word can be reached from more than one of the code...
A de Bruijn covering code of radius R is a binary string so that the set of words appearing as n consecutive symbols (wi
v1.3 research notesChung/: A de Bruijn covering code of radius R is a binary string so that the set of words appearing as n consecutive symbols (with wrap-around) is a c...
Is there a word which is unavoidable over a k letter alphabet, but not a (k-1) letter alphabet, for each integer k > 1
v1.3 research notesIs there a word which is unavoidable over a k letter alphabet, but not a (k-1) letter alphabet, for each integer k > 1? See this....
For each k and every sufficiently large n with k dividing ((n-1) choose (k-1)), there is a universal cycle for the k-sub
v1.3 research notesChung/Diaconis/Graham: For each k and every sufficiently large n with k dividing ((n-1) choose (k-1)), there is a universal cycle for the k-subsets of...
There is (essentially) a unique sequence over {1,2} which is its own run-length encoding
v1.3 research notesKolakoski: There is (essentially) a unique sequence over {1,2} which is its own run-length encoding. Is the density of 1's in this sequence 1/2? See t...
Is it true that, for some k, if all (K-1)-words are encountered by a t-ary word at the same rate as a uniform random t-a
v1.3 research notes/Rorabaugh: Is it true that, for some k, if all (K-1)-words are encountered by a t-ary word at the same rate as a uniform random t-ary word, then this...
start at (0,0), at each point in time, we take a step from (x, y) to (x+1, y), (x-1, y), (x, y+1), or (x, y-1) with prob
v1.3 research notesConsider the following walk: start at (0,0), at each point in time, we take a step from (x, y) to (x+1, y), (x-1, y), (x, y+1), or (x, y-1) with proba...
Consider p(v, t), the probability that a walk beginning from the origin ends at the point v on the d-dimensional integer
v1.3 research notes/Spencer: Consider p(v, t), the probability that a walk beginning from the origin ends at the point v on the d-dimensional integer lattice in time t. ...
What is the threshold function n = f(k) for the event that a random permutation on n symbols contains all patterns on k
v1.3 research notesAlon: What is the threshold function n = f(k) for the event that a random permutation on n symbols contains all patterns on k symbols? Conjecture: f(k...
What is the probability that a random nXn matrix over Z_(p) has zero permanent as n goes to infinity
v1.3 research notesTao: What is the probability that a random nXn matrix over Z_(p) has zero permanent as n goes to infinity? (Surely 1/p... as long as p is not 2.)...
Let f(p;n,k) = C(n,k) p^(k) (1-p)^(n-k)
v1.3 research notesGalvin: Let f(p;n,k) = C(n,k) p^(k) (1-p)^(n-k). If p is not 0, 1/2, or 1, is it possible for f(p;n,k) = f(p;n,l) and f(p;n,k') = f(p;n,l') for distin...
Is the exponent of matrix multiplication 2
v1.3 research notesIs the exponent of matrix multiplication 2? In other words, can two n b n matrices be multiplied in O(n^(2+)^(ľ)) steps? See this....
If A is an invertible n x n matrix, is there always an n x n submatrix B of [A A] so that perm(B) is nonzero
v1.3 research notesKahn: If A is an invertible n x n matrix, is there always an n x n submatrix B of [A A] so that perm(B) is nonzero. The notation perm(B) means the per...
Let S_(n) be a subset of 2^(n), interpreted as a family of truth assignments to x_(1)
v1.3 research notes: Let S_(n) be a subset of 2^(n), interpreted as a family of truth assignments to x_(1),...,x_(n). Let S_(n)-SAT be the problem of determining satisfi...