Questions tagged [combinatorics]

The tag has no usage guidance.

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k 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 ...
72 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 ...
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 ...
121 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 ...
223 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 ...
103 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 ...
116 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 ...
69 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 ...
59 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 ...
133 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 ...
332 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 ...
89 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 ...
160 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, ...
66 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....
45 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 ...
86 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 ...
116 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-...
68 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 ...
60 views

Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading:  Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 of [...
101 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 ...
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 ...
320 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 ...
234 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 ...
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at MathOverflow A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is ...
Given a graph $G=(V,E)$, a set of terminals $T = \{t_1,\ldots, t_n\}$, and a single source $s$, where $s\in V$ and $T \subseteq V\backslash \{s\}$. Each terminal $i$ is associated with a demand $d_i$ ...