All Questions
Tagged with co.combinatorics computer-science
128 questions
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
- 343
81
votes
4
answers
8k
views
Wanted: a "Coq for the working mathematician"
Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar with....
- 33.8k
64
votes
1
answer
5k
views
How to be rigorous about combinatorial algorithms?
1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...
- 33.8k
36
votes
8
answers
3k
views
Examples of errors in computational combinatorics results
I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
35
votes
12
answers
4k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
30
votes
1
answer
3k
views
An edge partitioning problem on cubic graphs
Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
- 1,164
27
votes
3
answers
2k
views
Expected edit distance
The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{...
user32786
22
votes
9
answers
17k
views
Fast evaluation of polynomials
Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
- 1,654
20
votes
5
answers
1k
views
Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)?
Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:
If $L$ is regular, then $f_L$ is ...
- 118k
18
votes
3
answers
785
views
Automated search for bijective proofs
In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...
- 82.7k
17
votes
0
answers
449
views
Splay trees and Thompson's group $F$
( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...
- 992
16
votes
9
answers
1k
views
Combinatorial constructions found by computer
In preparation for a talk I am giving to our undergraduate mathematics society, I am trying to collect examples of combinatorial constructions that were found by computer. Thus my question is the ...
15
votes
7
answers
1k
views
Two questions from combinatorics on words
Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...
- 2,135
15
votes
3
answers
2k
views
Why does the bitxor function appear in Nim?
I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...
- 1,129
13
votes
1
answer
799
views
Bipartite Nim-Geography
Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...
- 8,688
13
votes
1
answer
597
views
Does Langton's ant cover every n by 6 gridded torus?
This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus.
For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs ...
13
votes
0
answers
257
views
Is the set of power matrices decidable?
Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...
- 48.9k
12
votes
1
answer
1k
views
Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.
Consider functions on the discrete cube $\{-1,1\}^n$.
We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of co-...
11
votes
1
answer
696
views
I am searching for the name of a partition (if it already exists)
I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a ...
- 143
11
votes
1
answer
860
views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
- 1,088
10
votes
0
answers
175
views
A combinatorial proof of the Harrow--Kolla--Schulman theorem
Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$.
For integers $0 \leq k \leq n$, define a ...
- 679
9
votes
1
answer
425
views
Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
- 6,741
9
votes
1
answer
1k
views
9
votes
1
answer
594
views
Spanning $k$-trees
##k-trees
A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)
a) A complete graph with $k$ vertices is a $k$-tree.
b) A $k$-tree on $n$ vertices $T$ is obtained by a $...
- 24.7k
9
votes
1
answer
154
views
Inductive and reducible functions
The question was asked by a Computer Scientist and is closely related to parallel computing. But it is clearly of algebraic nature, so I decided to post it here.
Let $X$ be a set and $\bar X$ be the ...
user6976
9
votes
0
answers
2k
views
Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere
Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
- 311
9
votes
0
answers
759
views
Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another
Please consider the set of all possible strings of some finite size $M$ alphabet $\Sigma$, $\alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|\alpha| = L$. The Levenshtein distance (or 'edit ...
8
votes
1
answer
2k
views
Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice
Please imagine a discrete random walk on an N-dimensional rectangular lattice with dimensional lengths $(l_1, ..., l_N) \in L$ and total lattice points $P = \prod{l_i}$, for $i = 1, ..., N$. At each ...
- 599
8
votes
2
answers
1k
views
A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image
I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 ...
- 191
7
votes
1
answer
805
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
7
votes
1
answer
357
views
How long are the certificates produced by the Zeilberger and WZ methods for solving combinatorial sums (A=B)?
In the book "A = B" by Petkovesk, Wilf, and Zeilberger, (downloadable here), the authors provide several algorithmic methods for finding closed forms or recurrences for sums involving e.g. binomial ...
- 23k
7
votes
3
answers
500
views
Minimum number of swaps needed to 'group' a sequence?
Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
- 1,216
7
votes
1
answer
304
views
"Separated" version of Sauer's lemma on VC classes
Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...
- 2,207
7
votes
1
answer
270
views
Search algorithms with mappings/functions/sets as variables
I apologize in advance if this sounds vague but I am trying to find directions as to what to look for.
All the sets in this problem are finite.
Suppose we have two functions $f_1\colon X_1\times Y_1\...
- 173
6
votes
2
answers
729
views
Shifting an irrational binary sequence
Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be ...
- 48.9k
6
votes
1
answer
352
views
Number of partitions whose blocks form arithmetic progressions
As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...
- 24.8k
6
votes
2
answers
1k
views
Bijective proof of weak form of Stirling's approximation
There are short and sweet proofs of various forms of Stirling's approximation. But even the sweetest among them don't instill the same conviction in the reader as a direct bijective proof.
Computer ...
- 2,071
6
votes
1
answer
239
views
Algorithm that generates a n-simplex that cover n-polytope?
Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?
- 161
6
votes
1
answer
458
views
Applications of small Kakeya sets over finite fields
It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$.
For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
- 1,197
6
votes
1
answer
135
views
Generalising the adherence operator and its closure properties with regard to regular (rational) languages
Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-...
- 798
6
votes
1
answer
527
views
Can information be extracted more precisely using more random trials?
Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?
6
votes
1
answer
165
views
Separating infinite words sharing factors by automata
Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.
Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...
- 798
6
votes
0
answers
217
views
Nonclassical polynomials, circles, and groups
Tao and Ziegler have introduced a generalization of polynomials over a prime field called nonclassical polynomials, useful for studying the Gowers norm.
A nonclassical polynomial of degree $d$ is a ...
- 539
6
votes
0
answers
690
views
Unique Nash equilibrium games
Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
- 399
6
votes
0
answers
805
views
How many 2L-bit numbers are the product of two L-bit numbers?
If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of ...
- 375
5
votes
2
answers
500
views
How to construct particular De Bruijn sequences
For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples:
...
- 3,443
5
votes
1
answer
2k
views
Decomposition of a complete graph into maximal matching subgraphs
Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices $V=${1,2,3,4}...
- 377
5
votes
1
answer
264
views
Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$
Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b "=...
- 48.9k
5
votes
1
answer
276
views
NP-hardness of a sequence problem
Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
- 367
5
votes
1
answer
230
views
Cycling through $\{0,1\}^{(2^n)}$ such that all Hamming distance appear equally frequently
Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$....
- 48.9k