# Questions tagged [combinatorics]

The tag has no usage guidance.

45 questions
Filter by
Sorted by
Tagged with
77 views

### Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
43 views

### Relation between automorphism group of a linear code and its dual code

Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc. In ...
28 views

### Best known bounds on feedback arcset in high-girth directed graphs?

I asked this question over at MathOverflow, but thinking about it a little more I think it is a more natural fit here. Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every ...
63 views

### Combinatorial problems in electronics

This could be a downvoted question but I am asking because I am not able to get usable info via Google. Are there any interesting combinatorial problems in the field of electronics circuits design? I ...
51 views

### weights in low density codes

Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
47 views

### Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading: [1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 ...
55 views

### Complexity of Block Design?

What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)? I've found one paper that creates approximately solutions using Metaheuristics that claims ...
102 views

59 views

### s,t-Graphs representing infinite number of addition chains

I am looking at directed acyclic multi-graphs $G=(V,E)$ with a single source and sink with integer labeled arcs. Each vertex has exactly two inputs except $s$. Each vertex has at least one output ...
118 views

### Reducing resource allocation problem to bipartite matching

There are a set of bins, $B$ and a set of resources $R$. Each $b \in B$ is associated with a set function $Z_b(S) : 2^R \rightarrow \mathbb{R}^+$. The resource allocation problem is to find a ...
115 views

### Results/concepts that also proved useful outside of their “home areas”

There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used ...
182 views

311 views

### Counting distinct set covers

I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the ...
108 views

### On number of disjoint sets with small stack depth in a set of permutations

Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]), What is ...
107 views

### What's a good advanced textbook/resource for studying the complexity of counting and combinatorics?

I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not ...
107 views

### Partitions on Integer Permutations

Let $S_n$ be the set of all permutations of integers from $1$ to $n$. Let $P_1$ and $P_2$ be two partitions defined on $S_n$ as follows. $P_1$ is the set of all those permutations which have even ...
78 views

451 views

### Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no ...
222 views

### A non-trivial combinatorial optimization

So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be ...
177 views

### Locally monotone Boolean function

I am unable to understand the definition of locally monotone Boolean function which is defined in Gotsman and Linial, "Spectral Properties of Threshold Functions", 1994, p. 40: A function $f$ is ...