Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
10
votes
1answer
478 views

Finite One-Way Permutation with Infinite Domain

Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s ...
10
votes
2answers
390 views

Maximum imbalance in a graph?

Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average ...
10
votes
1answer
3k views

Minimum path covering problem

We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the ...
10
votes
1answer
364 views

What is the largest gap between rank and approximate rank?

We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication ...
10
votes
4answers
507 views

Interesting functions on graphs that can be efficiently maximized.

Say that I have a weighted graph $G = (V,E,w)$ such that $w:E\rightarrow [-1,1]$ is the weighting function -- note that negative weights are allowed. Say that $f:2^V\rightarrow \mathbb{R}$ defines a ...
10
votes
1answer
540 views

Determine the minimum number of coin-weighings

In the paper On two problems of information theory, Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins. ...
10
votes
1answer
1k views

$\epsilon$-nets with respect to the cut norm

The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
10
votes
1answer
253 views

Boolean error correcting code over $\mathbb{F}_q$

Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, ...
10
votes
1answer
257 views

Generating graphs of girth $g$ such that the minimum cycles form a double edge cover

Let $g\geq 3$. I need to generate simple graphs $G$ of girth $g$ such that the set of all $g$-cycles forms a double edge cover of $G$ (that is, every edge is shared by exactly two $g$-cycles), and ...
10
votes
1answer
228 views

Computing the union closure

Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$. The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking ...
10
votes
1answer
347 views

Regular high-girth graph with a "locally uniform" total order on nodes

Definitions Let $\epsilon > 0$ and let $d$, $r$, and $g$ be positive integers (with $g > 2r+1$). Let $G = (V,E)$ be a simple, $d$-regular, undirected, finite graph with girth at least $g$. Let $\...
10
votes
0answers
291 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] + \sum_{l=1}^{n-1}\sum_{...
10
votes
0answers
440 views

Relation beween approximate degree of a function and its Fourier coefficient.

Consider a Boolean function $f:\{0,1\}^n\to\{0,1\}$. The degree of the function $d$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than $d$...
10
votes
0answers
440 views

Expectation of Gowers norm

This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem: Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow \...
9
votes
3answers
2k views

What kind of mathematical background is needed for graph theory?

It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years? Which subjects should be ...
9
votes
2answers
308 views

Drawing graphs of bounded crossing number

Fáry's theorem says that a simple planar graph can be drawn without crossings so that each edge is a straight line segment. My question is whether there is an analogous theorem for graphs of bounded ...
9
votes
2answers
290 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 ...
9
votes
2answers
611 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 ...
9
votes
2answers
524 views

Extensions of Ramsey's theorem: monochromatic but diverse

As a follow-up of my previous question, which was resolved by Hsien-Chih Chang, here is another attempt to find an appropriate generalisation of Ramsey's theorem. (You don't need to read the previous ...
9
votes
1answer
278 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 ...
9
votes
2answers
344 views

A variation on discrepancy involving random graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
9
votes
2answers
990 views

Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
9
votes
2answers
212 views

Existence of "colouring matrices"

Edit: there is now a follow-up question related to this post. Definitions Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$. A $c \times c$ matrix $M = (m_{i,j})$ is said to be ...
9
votes
1answer
187 views

Does a pair of disjoint homotopic cycles in the dual separate the graph?

Let $G$ be a graph embedded on an orientable compact surface of genus $g$ so that the embedding is cellular. Consider the dual of the graph $G^*$. Let $C_1$ and $C_2$ be disjoint cycles in $G^*$ that ...
9
votes
1answer
432 views

Understanding the talks in Conferences and Workshops

I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors. At the end of the talk as usual some people ...
9
votes
1answer
529 views

Help on the following combinatorial problem?

I have $m$ bit vectors, each of which is composed by $m$ bits. Let's denote with $v_i[j]$ the $j$-th bit of the $i$-th vector, $i,j \in [1, m]$. Each bit vector $v_i$ is subject to the following 2 ...
9
votes
1answer
2k views

What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?

$k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that ...
9
votes
3answers
584 views

How many words of length $k$ on $l$ letters avoid a partial word?

EDITED TO ADD: This question is now essentially answered; please see this blog entry for more details. Thanks to everyone who posted comments and answers here. ORIGINAL QUESTION This is a hopefully ...
9
votes
2answers
336 views

Are there any 'graphical' algebras that can describe the 'shape' of graphs?

One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a ...
9
votes
1answer
366 views

Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
9
votes
1answer
295 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)$ ...
9
votes
1answer
423 views

Increasing the capacity to maximize the min cut

Consider a graph with all edges having unit capacity. One can find the min cut in polynomial time. Suppose I am allowed to increase the capacity of any $k$ edges to infinity (equivalent to merging ...
9
votes
1answer
307 views

Bounding the number of edges between star graphs such that graph is planar

I have a graph $G$ which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let $H_1, H_2, \ldots, H_n$ be different star graphs of ...
9
votes
0answers
207 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}$...
9
votes
0answers
117 views

Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

Consider the space $\mathbb{Q}^n$. A convex polyhedron is defined, equivalently, by a system of linear (in)equalities (with integer coefficients) or by a system of generators: vertices, and in case ...
9
votes
0answers
508 views

How to prove "obvious" facts?

The title is somewhat "arrogant": say, most of us treat $P\neq NP$ as an "obvious" fact, albeit no proof is in sight. But my question is at a much, much lower level, is about a fact which "should be" ...
9
votes
0answers
121 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}$ ...
9
votes
0answers
496 views

Statistical relationship between diameter and density in strongly connected random digraphs

I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the ...
9
votes
0answers
286 views

Spectral gap for random bipartite regular graphs

For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where $A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm ...
8
votes
2answers
268 views

A square with entries whose adjacencies never repeat

Suppose we have an $n \times n$ square, and an alphabet $\Gamma$. We put an element of $\Gamma$ in each location of the square. An element can appear in more than one location. The constraint is ...
8
votes
2answers
579 views

Grid minor in digraphs

Thor Johnson, et al, in their paper: Directed Tree Width, introduced a definition for directed grid $J_k$, and they conjectured: $(5.1)$ For every integer $k$ there exists an integer $N$ such that ...
8
votes
1answer
589 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 ...
8
votes
3answers
2k views

Cubic graphs and hamiltonian paths

I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you
8
votes
2answers
289 views

Is the cutting lemma true with O(r) lines?

The cutting lemma (a.k.a. cell decomposition lemma) states that given $n$ lines in the plane it is possible to divide it into $O(r^2)$ regions (even triangles) for any $1\le r\le n$ such that the ...
8
votes
2answers
460 views

Spectral techniques for genus of a graph

A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.
8
votes
1answer
292 views

Hamming weight of powers

Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$? If $e\log b$ bits are available, the number can ...
8
votes
1answer
500 views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
8
votes
2answers
2k views

Faster pseudo-polynomial time algorithms for PARTITION

I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...
8
votes
3answers
610 views

Constant in Komlos conjecture

Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\...
8
votes
3answers
290 views

How many sets of vectors can be represented as the solutions of a Horn-SAT instance?

Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE). In other words, a ...

1 2 3
4
5
13