Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [combinatorics]

The tag has no usage guidance.

56 questions
Filter by
Sorted by
Tagged with
2k views

### $\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years. You may recall that Hoffman and ...
322 views

### Minimum amount of colors preventing an equilateral uniformly colored subtriangle

In the Bundeswettberweb Infomatik 2010/2011, there was an interesting problem: For fixed $n$, find a minimal $k$ and a map $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that ...
• 607
334 views

### Distributing a binary relation into bins such that each element is in a small number of bins

We are given pairs of objects (say, numbers). Each object appears in at most $q$ pairs. Our goal is to distribute the pairs into equal-size bins, such that each object occurs in as few as possible ...
• 1,417
677 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 ...
• 295
194 views

• 641
136 views

### What is the standard name for the function which inflates a string by duplicating each of its characters?

Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters. For ...
299 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 ...
72 views

### Partition of a set of integers into subsets where the max. of the subset-sums is minimum

Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements. Let $\mathcal{P}$ denote the set of ...
108 views

### $k$-XOR collision free families

Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies: $\forall i: v_i\in\{0,1\}^{z_{n,k}}$. The bitwise xor ...
• 9,458
134 views

### VC dimension of Voronoi cells (Manhattan distance)

If the distance function originates from the Euclidean norm ($l_2$-norm), then the Voronoi diagram of $n$ points in a compact subset of $\mathbb{R}^d$ consists of cells that are convex polytopes. In ...
• 46
112 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 ...
• 387
61 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 ...
• 29
565 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 ...
134 views

### Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)

In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
344 views

### Which complexity information of Ising model is more important?

In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
• 641
91 views

### A number-theoretic bijection in modular arithmetic

Fix an integer $n$. Considered as a multiplicative group, the sets $A = (\mathbb{Z} / n \mathbb{Z})^*$ and $B = \mathbb{Z} / \phi(n) \mathbb{Z}$ have the same cardinality $\phi(n)$, but it does not ...
• 1,292
252 views

### Combinations over GF($q$)

Assume that we have $p$ finite sets ${m_1},{m_2},...,{m_p}$, with known cardinalities ${M_1},{M_2},...,{M_p}$, where $1 \le {M_i} \leq q$ ($i=1,2,...,p$). Each set contains (distinct) elements, ...
67 views

### Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: http://hal.inria.fr/docs/00/74/77/09/PDF/NonRedundantGeneration-TCS-2010....
• 2,359
1 vote
562 views

### Greedy vs LP Approximation

I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g....
• 171
1 vote
311 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 ...
• 23
1 vote
145 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 ...
• 41
1 vote
35 views

### Unclear relation in the number of permutations consistent with Hasse diagrams

I have been reading the paper 'Time Space Tradeoff for Sorting on Non-Oblivious Machines' by Borodin et al. (Link). Lemma 1 in that paper gives a relation between the number of permutations consistent ...
1 vote
57 views

### Is this a variant of the set cover problem?

$\textbf{Decision Problem:}$ Given a finite set of elements $E$ and a collection $C$ of non empty sets, $C=\{E_1,...,E_n\}$, such that each $E_i$ covers at least one element of $E$. The goal is to ...
1 vote
87 views

### Is there a "common" name for this type of combinatorial optimization problem?

I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next ...
• 11
1 vote
133 views

### Quantum error correction and graph codes

I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
• 387
1 vote
73 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 ...
• 223
1 vote
74 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 of [...
• 191
1 vote
107 views

### What are some examples where the Catalan numbers show up in algorithms/data structures?

For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
1 vote
111 views

### Binary Search Tree DELETE survey

In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree ...
• 2,359
1 vote
340 views

### Bin packing upper bound: total size of items = k, bin size = r

Suppose you have items, whose total size (i.e. sum of sizes) is $k$. The number of items and their individual sizes are unknown integers. We need to pack the items into bins of size $r$. I need to ...
• 31
1 vote
100 views

### PCVRP with prizes reduced over time

Hej guys, I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows: The set of customers does not change over time, but their respective prizes ...
• 113