ENUMERATION OF NON-CROSSING PAIRINGS ON BIT STRINGS (2009)
Todd Kemp, Karl Mahlburg, Amarpreet Rattan, Clifford Smyth
ABSTRACT. A non-crossing pairing on a bitstring matches 1s and 0s in a manner such that the pairing diagram is nonintersecting. By considering such pairings on arbitrary bitstrings 1 n1 0 m1
Enumeration of non-crossing pairings on bit strings (2009)
Kemp, Todd, Mahlburg, Karl, Rattan, Amarpreet, Smyth, Clifford
A non-crossing pairing on a bitstring matches 1s and 0s in a manner such that the pairing diagram is nonintersecting. By considering such pairings on arbitrary bitstrings $1^{n_1} 0^{m_1} ... 1^{n_r}...
On the variance of Shannon products of graphs (2007)
We study the combinatorial problem of finding an arrangement of distinct integers into the d-dimensional N-cube so that the maximal variance of the numbers on each ℓ-dimensional section is...
First Order Definability of Trees and Sparse Random Graphs (2005)
Bohman, Tom, Frieze, Alan, Luczak, Tomasz, Pikhurko, Oleg, Smyth, Clifford, Spencer, Joel, ...
Let D(G) be the smallest quantifier depth of a first order formula which is true for a graph G but false for any other non-isomorphic graph. This can be viewed as a measure for the first order...
Clifford Smyth, Abraham D. Flaxman
A permutation sum (resp. difference) set on a group G is a set F of bijections from G to G such that fg (resp. f −1g) is again a bijection for all f,g ∈ F (resp. f,g ∈ F with f � = g ∈ S),...
Irit Dinur, Oded Regev, Clifford Smyth
We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n 1/5) colors. Our result immediately...
Long monotone paths in line arrangements (2003)
József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
() N — = #+V ( * () =8-H S () = ()žŸŽi ’=;¡2 ’ ¢ ” £[ ¤ ¥ – œSH( *!Y
Reimer’s inequality and Tardos ’ conjecture (2001)
Let f: {0, 1} n → {0, 1} be a boolean function. For ɛ ≥ 0 let Dɛ(f) be the minimum depth of a decision tree for f that makes an error for ≤ ɛ fraction of the inputs x ∈ {0, 1} n. We also...
A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture (1999)
Abstract 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...