# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

580 questions
103 views

### Counting subsets of given set with certain properties

Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$. Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$, such that when the $s_i$ are ...
123 views

103 views

### Constructing a large bit-vector set with the following property

I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property: $$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$ In ...
290 views

An initially unknown string $x$ is known to be in $C\subseteq \{0,1\}^n$. Every round you are allowed to reveal one bit of $x$ (on your choice, and adaptively). How many bits do you need to reveal in ...
280 views

### expected number of edges for fixed min cut

It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges. Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
153 views

### A property of suffix-free regular languages of maximal state complexity for the reverse operation

Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of ...
275 views

### Enumerating all simply typed lambda terms of a given type

How can I enumerate all simply typed lambda terms which have a specified type? More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in ...
92 views

### reference request- property of subset of rows in a matrix

I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M ...
352 views

### Does the problem “partition a vertex-weighted graph into $k$ balanced connected parts” have a standard name?

Consider the following problem: Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, ...
209 views

### Number of local maxima in MAX-2-SAT

Given an instance of MAX-2-SAT, let us call an assignment of variables a "local maximum" if changing the value of any variable reduces the number of satisfied clauses. My question is, how many local ...
53 views

### Degree distribution of certain subgraphs of a biregular graph

Consider a bipartite graph $G=(X,Y)$, such that the degree of a left node $x \in X$ is $l$, and the degree of a right node $y \in Y$ is $r$. The number of edges is $|E|=|X|l=|Y|r$. Pick $w$ nodes in ...
133 views

### Computing Minima of the Projection of a Binary Cube

The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-...
209 views

### Can the “mutual independence” condition in the Lovász local lemma be weakened?

The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows. Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is ...
172 views

### Structured set of binary words

Definitions: Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$. For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that: Every element $e$ ...
220 views

### Pathwidth of planarized drawing of $K_{3,n}$

The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process: Draw it in the plane ...
105 views

### The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which ...
394 views

205 views

464 views

### Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
150 views

### Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description : $G$ is a $r$ regular ...
247 views

### Combinatorial discrepancy of the system of all cuts

This is a variant of this previous question. In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More ...
235 views

### Finding research problem for PhD(TCS)? [closed]

I am a theoratical computer science PhD student. I am wanted some suggestion in how to find research problem for PhD research. I have supervisor and he has given me first problem. We had get progress ...