Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
1
vote
2answers
95 views

Where to find info on (polytime) approximability of various discrete optimization problems?

Where to find info on (polytime) approximability of various discrete optimization problems? Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
-4
votes
1answer
30 views

does within the “range a and b” include a and b?

I have not found the answer to this doubt of mine elsewhere, hence posting it here. It may be a silly question but I just want to be sure :P would be great if someone could help me out with this ...
1
vote
0answers
59 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
1answer
84 views

Name of (and solution to) this generalization of linear assignment

I would like to know if the following problem is known and has any efficient solution. Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no ...
2
votes
1answer
85 views

NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
11
votes
3answers
448 views

Applications of sunflower lemma in theoretical computer science

In one lecture by Kewen Wu who is one of the authors of paper Improved bounds for the sunflower lemma, it is said that the sunflower lemma can be applied to many fields like circuit lower bounds ...
2
votes
2answers
116 views

On the coloring number of small graphs with small cliques

Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i....
0
votes
1answer
52 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 ...
1
vote
1answer
64 views

Existence of graphs of every order related to Barnette’s conjecture

Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
4
votes
1answer
185 views

Level $k$ bounds in Analysis of Boolean functions

In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears: If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer ...
3
votes
1answer
165 views

Dual to hypercontractive inequality

Recall the hypercontractive inequality: Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$ In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the ...
4
votes
1answer
233 views

How tight is the XOR lemma?

The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
6
votes
1answer
279 views

Re-packing of integers into fixed-size bins

We are given a constant $B \geq 3$, a set of positive integers $I$ s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$, and 2) a packing of these numbers into $N/B > 1$ bins of size $B$. An ...
-1
votes
1answer
61 views

Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]

I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems. As someone who is somewhat unfamiliar with the language of ...
0
votes
0answers
48 views

choosing the best subset where the metric is based on pairwise relationship

I want to model the competition between agents. Say there is a set of agents, and at each time step each agent $i \in \{0,1,\cdots, n-1\}$ can select a nonnegative number $x_i$ from a given range $[0,...
1
vote
0answers
88 views

Shortest s-t Path with a covering constraint

Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$; a source $s\in V$ and a sink $t\in V$; a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding ...
5
votes
1answer
239 views

The asymptotic behavior of a recurrence related to stable matchings

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows: $$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$ Apparently, Knuth was able to prove that ...
2
votes
0answers
128 views

Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
2
votes
1answer
85 views

Placing color boxes on a colored image such that color consistency is maximized

I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem. Given an image with black background that contains blobs whose ...
0
votes
0answers
66 views

Lower bound for permutation generator

I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections. Given $n$ inputs numbered $1 ......
1
vote
1answer
75 views

How to play the following game? (placing balls into bins)

Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$. The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\...
4
votes
1answer
188 views

Which (almost) balanced Boolean function has smallest “total” influence

The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$ $$ \max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
3
votes
2answers
168 views

Compactness of domino tilings

I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
3
votes
0answers
41 views

Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
4
votes
0answers
72 views

Optimal scheduling with delay constraints

Suppose you have $K$ servers numbered $\{1,2,...,K\}$. Playing server $i$ provides a value of $v_i > 0$. However, once you play server $i$, you are not allowed to play it for the next $n_i$ time-...
3
votes
0answers
71 views

Complexity of counting Wang tiles

Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
1
vote
0answers
125 views

Star seperators to explain computational complexity of algorithms on a class of graphs?

A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
4
votes
1answer
107 views

Stable order on binary strings

I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the ...
0
votes
1answer
150 views

Subset Sum Problem and hard looking instances that are not really hard

I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
4
votes
1answer
116 views

Applications of Christol theorem

I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
1
vote
1answer
85 views

Pulling a graph across a partition

I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
9
votes
0answers
169 views

Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs. Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
2
votes
0answers
138 views

Smallest disjoint union chain containing a sequence of sets

Let $\mathcal{A}=\{A_1,\ldots,A_n\}$ be a family of sets, we have the property that $A_1=\emptyset$, and one can obtain $A_i$ from $A_{i-1}$ by adding or deleting a single element. A family $\...
3
votes
0answers
82 views

Linear optimization over intersection of totally unimodular matrices

I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&&...
1
vote
0answers
104 views

Growth of random square lattice trees

Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
6
votes
1answer
124 views

Average-case analogue of Small-bias Spaces

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias $$| \mathbb{E}_{x \in S} [ (-...
3
votes
1answer
138 views

Mutually exclusive replacement paths, an existing problem?

A replacement path is a simple path allocated to an edge $e \in G$ that connects the endpoints of $e$ in $G \setminus \{e\}$. The problem An undirected graph $G$ is given and the task is to allocate ...
4
votes
1answer
112 views

Probability of a $k$-path in a random graph

Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$, the following fact is well known: \begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\...
1
vote
1answer
107 views

Total flow using minimum number of edges on a bipartite network

If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
1
vote
0answers
72 views

Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3

By a "chain of k nodes", I mean k nodes lined up like a linked-list: o-o-o.....-o . By "do not contain a sub-chain of length >=3", I mean that no cover should contain two edges that shares a node. ...
7
votes
1answer
266 views

Distinguishability a set of permutations

Given integers $d<n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is ``distinguishable''...
1
vote
0answers
31 views

Inductive definition of language operators like the set of all permutations of a word came from the shuffle operator

Let $X$ be a finite alphabet. Given two words $u, v \in X^{\ast}$ the shuffle operator is defined to be $$ u || v := \{ u_1 v_1 u_2 v_2 \ldots u_n v_n : 1 \le i \le n, u_i, v_i \in X^{\ast}, u = u_1 \...
1
vote
2answers
357 views

Is perfect matching for bipartite graph with no cycles unique?

Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching. My question is if the balanced bipartite graph is also ...
1
vote
0answers
158 views

How to represent boolean tree + algorithm as a mathematical formula

In programming say you have a boolean tree like this: ...
-1
votes
1answer
150 views

Application of the inequality with expectations

Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
1
vote
0answers
80 views

Nim-game variant - weird ending condition

the game is structured like this: two players the players alternate moves 4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$ at each move, the player can either remove one or two elements from ...
4
votes
2answers
314 views

NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
3
votes
2answers
5k views

How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once. For a subset $S$ of nodes and a node $i\in S$, let $D[...
-3
votes
1answer
155 views

Continous work distribution algorithm with failover

Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256. Is there an algorithm that ...
-3
votes
1answer
147 views

Proving that a random permutation generator is not fair [closed]

If I'm generating random permutations using the following algorithm: ...

1
2 3 4 5
12