Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

581 questions
105 views

$n^2 x n^2$ Sudoku Puzzles have equal amount of easy-instances that can be solved in $O(n^k)$ time, under experimentation so far this is correct

Introduction I found out that I can take any $n^2 x n^2$ puzzle, solve it and study its permutation pattern and implement it into a poly-time Sudoku Generator. I also found out that a limited subset ...
164 views

102 views

Mutually exclusive replacement paths, an existing problem?

A replacement path is a simple path allocated to an edge $e \in G$ that connects the endpoints of $e$ in $G \setminus \{e\}$. The problem An undirected graph $G$ is given and the task is to allocate ...
5k views

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
142 views

Compactness of domino tilings

I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
285 views

68 views

Complexity of counting Wang tiles

Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
3k views

LP relaxation of independent set

I've tried the following LP relaxation of maximum independent set $$\max \sum_i x_i$$ $$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$$ $$x_i\ge 0$$ I get $1/2$ for every variable for every cubic ...
123 views

Star seperators to explain computational complexity of algorithms on a class of graphs?

A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
4k views

The origin of the notion of treewidth

My question today is (as usual) a bit silly; but I would request you to kindly consider it. I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
89 views

Stable order on binary strings

I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the ...
142 views

Subset Sum Problem and hard looking instances that are not really hard

I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
112 views

Applications of Christol theorem

I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
78 views

Pulling a graph across a partition

I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
134 views

Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs. Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
134 views

116 views

147 views

Application of the inequality with expectations

Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
135 views

How to represent boolean tree + algorithm as a mathematical formula

In programming say you have a boolean tree like this: ...
1k views

Number of distinct nodes in a random walk

Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically ...
652 views

Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up sometimes, ...
310 views

Are there any 'graphical' algebras that can describe the 'shape' of graphs?

One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a ...
173 views

Difference Sets

Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N}$$ and $p_k$'s are distinct. We calculate the differences as: d=p_i-p_j\mod ...
74 views

Nim-game variant - weird ending condition

the game is structured like this: two players the players alternate moves 4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$ at each move, the player can either remove one or two elements from ...
277 views

On the notion of positive rank

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, ...
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...