# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

628 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
1k views

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_{...
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$...
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 \... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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$... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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)$... 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 ... 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 ... 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}$... 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 ... 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" ... 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}$... 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 ... 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 ... 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 ... 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 ... 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 ... 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 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 ... 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. 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 ... 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. ... 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 ... 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$\...
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 ...