Questions tagged [combinatorics]
The combinatorics tag has no usage guidance.
56
questions
23
votes
0
answers
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 ...
13
votes
2
answers
320
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 ...
11
votes
1
answer
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 ...
7
votes
2
answers
675
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 ...
6
votes
2
answers
193
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 ...
6
votes
1
answer
151
views
Directed graph with bounded in-deg can be partitioned in a balanced way
I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
5
votes
1
answer
214
views
Name for words without squared symbols
Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
5
votes
3
answers
302
views
Probability for an element to appear in at least one set
Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct.
What is the ...
5
votes
0
answers
87
views
Does every graph of clique-width 3 have a large induced subgraph of clique-width 2?
Is there a constant $\alpha>0$ such that every graph $G$ of clique-width $3$ and order $n$ has an induced subgraph of order at least $\alpha n$ and clique-width at most $2$ (in other words, the ...
4
votes
1
answer
419
views
Enumerating all simply typed lambda terms of a given type
How can I enumerate all simply typed lambda terms which have a specified type?
More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in ...
4
votes
1
answer
181
views
Concrete version of KKL Theorem
The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function $f:\{−1,1\}^n→\{−1,1\}$ we have $\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$. I am looking for a ...
4
votes
1
answer
638
views
Interesting real life problem similar to subsetsum /bin packing problem
I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :
I have large number of cable reels/drums (let's ...
4
votes
1
answer
264
views
Möbius values of CNF and DNF lattices of a monotone Boolean function
Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $...
3
votes
2
answers
2k
views
Binary rank of binary matrix
Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \...
3
votes
1
answer
124
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 ...
3
votes
1
answer
217
views
Cover a graph with complete graphs
I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
3
votes
1
answer
81
views
Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ?
$$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$
Second question: if it is possible that every $L$...
3
votes
0
answers
110
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 ...
3
votes
0
answers
125
views
Social choice theory, preference aggregation data sets
I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social ...
3
votes
0
answers
228
views
Optimization of class schedule
I am creating a scheduling program that I need to either optimize or prove that what I have is already optimal.
I have n groups, all of which need to do some activity a in time slot t. A person can ...
2
votes
1
answer
227
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 ...
2
votes
1
answer
88
views
Complexity of generating a pseudo-Boolean function
A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to
$\mathbb{R}$.
Following is a pseudo-Boolean function.
$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - ...
2
votes
1
answer
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 ...
2
votes
1
answer
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 ...
2
votes
0
answers
67
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 ...
2
votes
0
answers
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 ...
2
votes
0
answers
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 ...
2
votes
0
answers
110
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 ...
2
votes
0
answers
60
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 ...
2
votes
1
answer
560
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 ...
2
votes
0
answers
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 ...
2
votes
0
answers
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 ...
2
votes
0
answers
90
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 ...
2
votes
0
answers
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, ...
2
votes
0
answers
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....
1
vote
1
answer
556
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....
1
vote
1
answer
309
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 ...
1
vote
1
answer
143
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 ...
1
vote
0
answers
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
0
answers
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
0
answers
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 ...
1
vote
0
answers
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-...
1
vote
0
answers
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 ...
1
vote
0
answers
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 [...
1
vote
0
answers
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
0
answers
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 ...
1
vote
0
answers
339
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 ...
1
vote
1
answer
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 ...
0
votes
1
answer
55
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 ...
0
votes
1
answer
124
views
An algorithm for counting to Graham’s Number
I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory.
I thougth of the way to organize counter suitable for ...