# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

628 questions
Filter by
Sorted by
Tagged with
215 views

104 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 ...
298 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 ...
317 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$ ...
159 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 ...
344 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 ...
96 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 ...
588 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, ...
244 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 ...
65 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 ...
142 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\}$-...
293 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 ...
181 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$ ...
279 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 ...
110 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 ...
597 views

218 views

624 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 ...
155 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 ...
259 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 ...
299 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 ...
265 views

### What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
537 views

I encountered the following result during my research. $$\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1$$ where $m=\omega(\sqrt n)$ and $a_1,\... 1answer 248 views ### Compute lowest dimensional polytope from a given set of sign vectors Given a set of hyperplanes determined by the normal vectors$h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors$t\in\{+,-\}^m$for which there exists a vector$v\in\...
Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different ...
### $d$-regular bipartite expander graph
I have seen that there exists $d$-left regular bipartite graphs. My question is do there exists $d$-regular bipartite expander graphs in which both the degree of the left and the right vertices is ...