
Recent Activity
Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★
Author(s): Feige


Given is a 3SAT (3CNF) formula on
variables, for some
, and
clauses drawn uniformly at random from the set of formulas on
variables. Return with probability at least 0.5 (over the instances) that
is typical without returning typical for any instance with at least
simultaneously satisfiable clauses.
Keywords: NP; randomness in TCS; satisfiability
Does the chromatic symmetric function distinguish between trees? ★★
Author(s): Stanley
Keywords: chromatic polynomial; symmetric function; tree
Shannon capacity of the seven-cycle ★★★
Author(s):

Keywords:
Magic square of squares ★★
Author(s): LaBar

Keywords:
Inverse Galois Problem ★★★★
Author(s): Hilbert

Keywords:
Seymour's r-graph conjecture ★★★
Author(s): Seymour
An -graph is an
-regular graph
with the property that
for every
with odd size.



Keywords: edge-coloring; r-graph
Edge list coloring conjecture ★★★
Author(s):



Keywords:
Kneser–Poulsen conjecture ★★★

Keywords: pushing disks
Wide partition conjecture ★★
Keywords:
3-accessibility of Fibonacci numbers ★★
Keywords: Fibonacci numbers; monochromatic diffsequences
Simplexity of the n-cube ★★★
Author(s):


Keywords: cube; decomposition; simplex
Crossing sequences ★★
Author(s): Archdeacon; Bonnington; Siran


Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with
crossings, but not with less crossings.
Keywords: crossing number; crossing sequence
The Crossing Number of the Complete Graph ★★★
Author(s):
The crossing number of
is the minimum number of crossings in all drawings of
in the plane.

Keywords: complete graph; crossing number
The Crossing Number of the Hypercube ★★
The crossing number of
is the minimum number of crossings in all drawings of
in the plane.
The -dimensional (hyper)cube
is the graph whose vertices are all binary sequences of length
, and two of the sequences are adjacent in
if they differ in precisely one coordinate.

Keywords: crossing number; hypercube
Monochromatic reachability or rainbow triangles ★★★
Author(s): Sands; Sauer; Woodrow
In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.




Keywords: digraph; edge-coloring; tournament
Rank vs. Genus ★★★
Author(s): Johnson
Keywords:
The Hodge Conjecture ★★★★
Author(s): Hodge


Keywords: Hodge Theory; Millenium Problems
2-accessibility of primes ★★
Keywords: monochromatic diffsequences; primes
Non-edges vs. feedback edge sets in digraphs ★★★
Author(s): Chudnovsky; Seymour; Sullivan
For any simple digraph , we let
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and
be the size of the smallest feedback edge set.



Keywords: acyclic; digraph; feedback edge set; triangle free