Tagged Questions

Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms (1)

6
votes
0answers
59 views

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
-1
votes
0answers
78 views

NP-hardness of the following problem

A subgraph $H \subseteq G$ is said to be 'valid' if all the paths in $H$ satisfy the property $x$. The property $x$ is closed under taking sub-paths. Given a directed graph $G$ and a set of all ...
-3
votes
0answers
113 views

A truly random secret-Santa generator

Our office are trying to create a truly-random secret-Santa generating algorithm. We've found only one other reference to this paradigm on an XKCD forum: ...
7
votes
1answer
171 views

A curious asymmetry in good characterizations

There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing ...
2
votes
0answers
32 views

Minimizing a general submodular pseudo boolean function

Are there algorithms that minimize a general submodular pseudo boolean function (PBF) without first transforming it to a quadratic pseudo boolean function (QPBF)?
2
votes
1answer
63 views

Weighted furthest point voronoi diagrams

I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that. But I could not find anything on Weighted furthest point voronoi diagrams !! But ...
5
votes
0answers
111 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
4
votes
0answers
160 views

Is this graph polynomial known? Can it be efficiently computed?

Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. [To be more explicit, given an edge $\ell$ ...
5
votes
0answers
82 views

General Results for Complicated Constraint Satisfaction Problem

Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ...
10
votes
0answers
183 views

Sign patterns for Fourier coefficients of Boolean functions

Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise. For a boolean function $f: \{0,1\}^n \to \{0,1\}$, ...
-1
votes
2answers
78 views

Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ ...
2
votes
0answers
56 views

Name for the “stronger submodularity” property in cut function

Let $f:2^V \rightarrow \mathbb{R}$ be a set function over $V$ that satisfies the following: $f(A \cap B) + f(A \cup B) \le f(A) + f(B)$ $f(A \backslash B) + f(B \backslash A) \le f(A) + f(B)$. ...
10
votes
0answers
128 views

Is RAMSEY COLORING in $NC$?

Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$. ...
5
votes
0answers
70 views

Perfect hashing family variation - injectivity on $r$ disjoint sets

We denote by $[t]$ the set $\{1,2,\ldots,t\}$. A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S ...
0
votes
0answers
79 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
28
votes
4answers
814 views

What is simplest polynomial algorithm for PLANARITY?

There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ...
4
votes
2answers
570 views

Sum of products of all combinations?

We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$. Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$). We want to compute the ...
8
votes
4answers
482 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems ...
0
votes
2answers
129 views

Determining the distribution of results of a simple algorithm

Setting Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$: Pick an integer $k \in N$, uniformly at random. Pick a subset of $k$ elements from $N$, uniformly at ...
4
votes
0answers
66 views

What is the smallest deterministic construction of an ordered perfect hashing family?

A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$. ...
9
votes
1answer
160 views

Random restrictions and the connection to total influence of Boolean functions

Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ ...
1
vote
0answers
92 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
2
votes
1answer
164 views

Literature for Generalized Load Balancing

i am looking for literature on this kind of problem. $$ \begin{align} \min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\ \text{subject to}&\\ &\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
10
votes
0answers
217 views

A bijection between ordered lambda terms and rooted planar maps?

Consider the following recurrence in two parameters $n$ and $k$: \begin{aligned} NF(0,k) &= 0 \\ NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\ Neu(n,k) &= [n=1 \wedge k=1] + ...
2
votes
1answer
68 views

Upper bound to number of closed itemsets

Given a set $I$ of $n$ items, and a collection $D$ of $m<2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper ...
8
votes
1answer
162 views

Multidimensional arithmetic progression variant

For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e. $Q(\vec{d} = ...
6
votes
3answers
184 views

Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

Consider the set of $n^2 - n$ pairs $\{(i, j)\ |\ i \neq j \leq n\}$. Call a partition $(P_1,\ldots,P_r)$ of this set valid if for each $P_t$, the sets $\{i\ |\ \exists k: (i,k) \in P_t\}$ and ...
0
votes
0answers
102 views

Edges in a graph with girth greater than 4

According to the following paper by Füredi, the maximum number of edges for a graph with $n$ vertices is upper bounded by $O(n^{\frac{3}{2}})$, where the leading co-efficient of the term ...
1
vote
1answer
149 views

More questions about permutations

I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically. the ...
5
votes
0answers
75 views

Upper bound on Euler characteristic of downward closed family

(Definition: $\mathcal{F}$ is called downward closed if for any $A \in \mathcal{F}$ and $B \subseteq A$ it holds that $B \in \mathcal{F}.$) Let $\mathcal{F}$ be a downward closed family of subsets of ...
2
votes
1answer
119 views

Faithful functors vs forgetful functors: exact category-theoretic defs?

In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the ...
10
votes
0answers
115 views

Sylver Coinage Game

A game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the ...
1
vote
0answers
83 views

Restoring symmetry in certain combinatorial bijections?

I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an ...
2
votes
0answers
75 views

Existence of bijective proofs involving Yamanouchi words?

The following notion comes from algebraic combinatorics and might have some connections to language/permutation theory. Fix an integer $k$. Let us call a $k$-Yamanouchi word a sequence $u$ of integers ...
2
votes
1answer
108 views

Upperbound the order of P3-free partition of P4-free graphs

A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free ...
7
votes
3answers
181 views

On the size of P4-transversals of graphs

A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices. ...
1
vote
1answer
156 views

Is there an analogy of a vertex separator for hypergraphs?

Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs. Is there some survey or book or lecture notes about ...
21
votes
2answers
1k views

Representing OR with polynomials

I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such: $p(x_1,\ldots,x_n) = 1-\prod_{i = ...
8
votes
1answer
448 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several ...
16
votes
0answers
368 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...
5
votes
1answer
119 views

Worst case ratio between minimum clique cover and maximum independent set

The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
3
votes
0answers
112 views

Building a “balanced” universal set

A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, ...
4
votes
0answers
77 views

Constructing a small (n,k)-Covering Matrices family

Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$. We call ${\cal A}$ a (n,k)-covering, if for every subset of columns $I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in ...
6
votes
1answer
224 views

Constructing a k-perfect permutations family

I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, ...
1
vote
0answers
62 views

Upper bound on the number of vertex-transitive graphs

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?
16
votes
0answers
173 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
3
votes
0answers
100 views

Concentration of Stationary Distribution on Random Directed Graphs

We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. ...
9
votes
0answers
106 views

Computing weighted sums of binomial coefficients

This question is a reformulation of Complexity for computing weighted number of paths on integer lattice Is there any way to compute in $o(n^2)$ all $n$ sums $\sum_{0\leq i \leq j} a_i\binom{j}{i}$ ...
3
votes
0answers
112 views

An identity about the Majority function?

Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x ...
1
vote
0answers
64 views

Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope

Definitions: Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector ...