# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

628 questions
Filter by
Sorted by
Tagged with
67 views

### Variation on Social Golfers

This is a problem I ran across recently while trying to schedule classes which I thought might be interesting theoretically. Given k golfers who want to play on <...
292 views

### Boolean circuits and digraphs

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the "...
476 views

### Identify all of the non-overlapping rectangular regions of a simple concave polygon

I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will ...
503 views

### Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
135 views

### Tractability of mutual information-augmented ensemble classification algorithms

I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an ...
186 views

### Indexing over all possible functions in better than linear time

Given two sets X and Y, the number of functions mapping X to Y is $\vert Y\vert^{\vert X \vert}$. In particular I am interested in binary strings of relatively small length, e.g. 8. There are $2^8$ (...
99 views

### How many subsets of size L do not contain the first k arbitrary pairs?

Let there be a large set $X$, and a bijective function $f$ which maps the integer range 1 to $|X| \choose 2$ onto the subsets of $X$ of size 2. Given integers $L$ and $k$, where $2 \leq L \leq |X|$ ...
324 views

### On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

I have 2 questions. Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph ...
57 views

### Regrouping a collection of sets based on constraint

(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.) Consider a collection of $N$ balls with subsets of $n_1, n_2, ..., n_L$ balls of different $L$ colors. The ...
129 views

### Counting subsets with large sum

Suppose that you have a multiset of positive integers $I$. $I$ is not given, but it is known that the sum over all elements of $I$ = $k$. (e.g. if $I$={2,5,7} then k=14 is given, but I is unknown). ...
83 views

### Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ ...
66 views

### Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]

I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems. As someone who is somewhat unfamiliar with the language of ...
158 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 ...
417 views

### Intersection between sets

Assume that we have $p$ sets, with given sizes: $m_1,m_2,...,m_p$. The (distinct) elements in each set are taken from $N$ elements (where $m_1,m_2,...,m_p \le N$). A combination is defined as an ...
165 views

### Representation suitable for reconstruction of a tree with bounded degree

I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
3k views

### Minimal perfect hash function from sets of integers to integers

I would like to be able to map any subset of $S = \{0,..,m-1\}$ to an integer $k$. $m$ will probably be 32 because $|\mathcal{P}(S)| = 2^m$ and i want to use a variable with 32 bits to store this ...
251 views

### Complexity of counting the number of Good-perfect matching in the bipartite graph

Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$. Definition1: ...
297 views

### Finding research problem for PhD(TCS)? [closed]

I am a theoratical computer science PhD student. I am wanted some suggestion in how to find research problem for PhD research. I have supervisor and he has given me first problem. We had get progress ...
246 views

### Lemma needed for my machine learning research [closed]

Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...
109 views

### Subset sum for lists [closed]

Given a target list a = [2,4,1,4]` and a list of lists ...
194 views

### Proving that a random permutation generator is not fair [closed]

If I'm generating random permutations using the following algorithm: ...
155 views

### Continous work distribution algorithm with failover

Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256. Is there an algorithm that ...
6k views

### unique binary tree from preorder and postorder traversals of a full binary tree [closed]

If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T. If so.. could ...
53 views

### does within the "range a and b" include a and b?

I have not found the answer to this doubt of mine elsewhere, hence posting it here. It may be a silly question but I just want to be sure :P would be great if someone could help me out with this ...
461 views

### Covering Codes with Game Theory Application

Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. I could not come up with an adequate solution, so here I am, asking ...
2k views

### Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
132 views

### A simple challenge

Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. ...