Questions tagged [combinatorics]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
80 views

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 ...
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 ...
102 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 ...
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-...
159 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 ...
68 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 ...
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 ...
53 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 ...
60 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 [...
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 ...
127 views

206 views