Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
597
questions
0
votes
1answer
45 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
442 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
115 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
51 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
60 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
182 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
164 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
232 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
278 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
236 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
163 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
71 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
115 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
167 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
80 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
103 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
123 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
133 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
70 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
265 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
344 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
157 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
77 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
312 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
144 views
Proving that a random permutation generator is not fair [closed]
If I'm generating random permutations using the following algorithm:
...
3
votes
0answers
87 views
Finding the longest sub-permutation with bounded inversion number
Given a permutation $\sigma\in S_n$ and a positive integer $k$, find the largest integer $0\le m\le n$ such that there exist a subset $I\subseteq [n], |I|=m$, satisfying that the restriction of $\...
4
votes
1answer
1k views
Is Hartmanis-Stearns conjecture settled by this article?
The paper
"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
https://arxiv.org/abs/1601....
9
votes
1answer
227 views
Finding subgraphs with high treewidth and constant degree
I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
