Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

1
vote
0answers
61 views

Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...
5
votes
0answers
124 views

Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
4
votes
1answer
253 views

Strings with no long runs from proper subalphabets

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...
6
votes
1answer
94 views

Sum identities with immanants

For $\chi$ being an irreducible character of the symmetric group $S_n$ and being $M$ a complex $n\times n$-matrix, I would like to show $$ \sum_{\sigma, \rho \in S_n} \overline{\chi(\sigma)} ...
5
votes
0answers
61 views

Uniform generation of Symmetric Plane Partitons

In the conclusion of An Involution Principle-Free Proof of Stanley's Hook-Content Formula Krattenthaler notes that the techniques of the paper might be useful for finding bijective proofs of the ...
1
vote
1answer
207 views

A Bernstein-like Combinatorial Sum

Do sums of the "convoluted Bernstein" form $$ \sum_{j=1}^m {m\choose j} q^j (1-q)^{m-j} {n \choose k} \left(\frac j m\right)^k \left(1- \frac j m\right)^{n-k} $$ admit closed forms? My attempts to ...
6
votes
0answers
291 views

What can I further assume about the speeds of runners of Lonely Runner Conjecture WLOG?

Lonely Runner Conjecture is the following problem, and the conjecture was proven to be true for $k\leq 7$: Let $V$ be the set of $k$ distinct positive integers with $v_1<v_2<...<v_k$ ...
5
votes
1answer
343 views

How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra. Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$ that one needs to take ...
2
votes
0answers
40 views

A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements. In a well celebrated paper Richard ...
23
votes
1answer
1k views

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
5
votes
1answer
255 views

A claim from “Graph minors - a survey” by Robertson and Seymour

Can someone give me a proof sketch for this: Let $\mathscr{P}_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type ...
31
votes
2answers
945 views

Random sequence of integers in $\{1, 2, \dots, n \}$ which is “everywhere probably increasing” - how long can it be?

Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$. Fix $r ...
4
votes
5answers
335 views

Table of planar connected graphs

For the other day I need to use the table of planar connected graph with few vertex. In the wolfram's mathworld , they listed only the graph with $4$ vertex. Does anyone knows webpages or pdf on the ...
1
vote
1answer
173 views

Singular homology of the zero loci of polynomials

I am very sorry but apparently I am really weak in cohomology flavored questions. I try to reformulate my problem in a very simple and hopefully clear way. This question is related with a problem in ...
1
vote
0answers
92 views

Are back edges mandatory in Ford Fulkerson algorithm?

Consider the algorithm of Ford Fulkerson where, for each iteration, you add flow along a path equal to the maximum residual capacity along this path. Does it exist, for every network, a choice of ...
11
votes
1answer
210 views

Complexity of planar scissor congruence

Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces. What can be said about the ...
2
votes
1answer
141 views

Linear independence of +/- 1 strings/vectors II

Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...
3
votes
2answers
244 views

Isoperimetric inequality on the Hamming cube

Suppose $X \subseteq \lbrace 0 , 1 \rbrace ^{m}$ such that $|X| \geq 2^{0.8m}$, and $m \geq 2$, then prove that there exists $x,y \in X$ with $||x - y||_{1} \geq m/2$. My approach to prove this was ...
7
votes
1answer
784 views

A Question about Palindromic Numbers and System of Arithmetic Progression

Based from Harminc and Sotak's result, www.fq.math.ca/Scanned/36-3/harminc.pdf We know that under certain condition, an arithmetic progression can contain an infinitely many palindromes. My question ...
1
vote
1answer
121 views

Linear independence of +/- 1 strings/vectors

Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...
3
votes
1answer
129 views

Simultaneous approximation by rationals with relatively prime numerators

The following seems hard to me (or perhaps just not true), but perhaps I am mistaken. It is known that given irrational numbers $x_1$ and $x_2$, there are infinitely many simultaneous rational ...
1
vote
1answer
107 views

Combinatorial polynomials from general diagram fillings?

There is a plethora of polynomials defined on partition shaped Young diagrams, (Schur, Jack, Grothendieck,...), and skew Young diagrams. There are also composition shaped diagrams that are responsible ...
1
vote
1answer
97 views

Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph. It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...
1
vote
4answers
616 views

Distribution of composite numbers

I have moved this question to math.stackexchange.com. People who are interested in this question can discuss at :http://math.stackexchange.com/questions/1272431/distribution-of-composite-numbers ...
5
votes
1answer
228 views

Dimension of the span of all partial derivatives of a given symmetric polynomial $f$ and the polynomial $E(f)$

I need some help on the problem below. Let $d\geq 4$ and $f$ a symmetric polynomial, homogeneous of degree $d$, in $n$ variables $x_1,\dots,x_n$, with real coefficients. We set $$ ...
4
votes
0answers
287 views

How is $ \sum_{x \in X(\mathbb{F}_q)} \dots $ a generalization of cardinality?

This quarter Maxim Kontsevich is offering a course on exponential integral. There is not much in the way of notes, but is one page with mysterious comments. Let $X$ be an algebraic variety over ...
3
votes
0answers
103 views

scalar multiple of Young symmetrizer

The following is a lemma from Fulton and Harris' book -Representation theory,a first course (page 53): Lemma: For all $x\in \mathbb{C}\mathfrak{S}_r$, $c_{\lambda}\cdot x\cdot c_{\lambda}= scalar ...
4
votes
2answers
178 views

Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is $$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...
10
votes
1answer
339 views

Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
1
vote
1answer
173 views

Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...
2
votes
0answers
140 views

Largest Fourier coefficient of sparse boolean function

Consider a Boolean function $f: GF(2)^n \rightarrow \{0, 1 \}$. I would like to show that if $f$ is sparse, i.e. $\sum f(i) \leq t$, then $f$ must have a large Fourier coefficient. (A Fourier ...
8
votes
1answer
160 views

Extending subsets to supersets in different ways

We are given a collection of sets $A_1,\ldots,A_s$, pairwise different and each of cardinality $k$, and a collection of sets $B_1,\ldots,B_s$, pairwise different and each of cardinality $l>k+1$, ...
5
votes
1answer
168 views

Graph of graph homomorphisms

For (finite or infinite) undirected, simple graphs $G, H$, let $V_{\text{Hom}} = \{f:G\to H:f\text{ is a graph homomorphism}\}$, and $E_{\text{Hom}} =\big\{\{f,g\}\subseteq V_{\text{Hom}}: ...
3
votes
1answer
181 views

Seymour's second neighborhood conjecture

Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.
2
votes
0answers
49 views

Decomposing a weakly chordal graph into disjoint union of co-chordal graphs

A graph G is said to be co-chordal if it is $\bar C_n$-free for any $n \ge 4$. It is weakly chordal if it is $C_n$ and $\bar C_n$ free for all $n\ge 5$. Assume that the induced matching number of $G$ ...
5
votes
1answer
138 views

Algorithm that generates a n-simplex that cover n-polytope?

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?
5
votes
0answers
62 views

Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.) 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 ...
5
votes
1answer
146 views

Integer decomposition of dilated integral polytopes

For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$. Question: Given $d > n + 2$ is it true that $$ ...
5
votes
1answer
151 views

A generalization of Erdős–Newman–Mirsky?

Given a sequence $S$ of natural numbers, write ${\bf Gap}(S)$ for the set of differences between consecutive terms. (So $|{\bf Gap}(S)|=1$ precisely for arithmetic progressions, hence the connection ...
25
votes
1answer
1k views

Combinatorics of K(Z,2)?

Anybody knows a semi-simplicial model for $K(Z,2)$ having finite number of simplexes in any dimension? With some regular description? I have heard about big activity on triangulating $CP^n$ but this ...
1
vote
0answers
38 views

Lattice-isotopic essentialization of arrangements

I'm working on a problem related to $\textbf{Randell's isotopy theorem}$ for complex hyperplane arrangements. I have a question which seems quite obvious. However, I haven't found a rigorous proof ...
11
votes
3answers
317 views

Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks). I will be thankful for answers ...
3
votes
1answer
143 views

An upper bound on the number of sets of parallel lines covering points in a finite plane?

Let $\mathbb{F}$ be a finite field of characteristic $2$. Let $L_m$ denote the set of lines in $\mathbb{F}^2$ with slope $m\in\mathbb{F}$, that is, all parallel lines of the form $y=mx+b$. Consider a ...
85
votes
7answers
4k views

Is the set $ AA+A $ always at least as large as $ A+A $?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$? My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
12
votes
2answers
737 views

Mysterious identity between numbers of odd/even meander systems

Definitions: An upper arch system of order $n$ is a subset of the plane consisting of $n$ non-intersecting closed semicircles in the upper half-plane whose endpoints belong to the set $\{(k,0)\mid ...
12
votes
2answers
657 views

A combinatorial question about orthonormal bases

Suppose that $F:S^{n-1}\to A$ is a map of sets from the unit sphere in $\mathbb R^n$ to an abelian group, and that the sum $F(v_1)+\dots +F(v_n)$ over an orthonormal basis is independent of the basis. ...
14
votes
0answers
195 views

Coloring a Ferrers diagram

I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed. Say that a coloring of the dots of a Ferrers ...
4
votes
0answers
134 views

Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path. A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
2
votes
2answers
348 views

Local coordinates on (infinite dimensional) Lie groups, factorization of Riemann zeta functions

Given a (finite dimensional) Lie group $G$ (real $k=\mathbb{R}$ or complex $k=\mathbb{C}$) and its Lie algebra $\mathfrak{g}$, one can prove (a basis $B=(b_i)_{1\leq i\leq n}$ of $\mathfrak{g}$ being ...
3
votes
1answer
146 views

A question of terminology regarding integer partitions

I am wondering if there is a standard notation and name for the following. Let $\lambda$ be a partition $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_r\geq 1$ of $n$ into $r$ parts. Then we can ...