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)

0
votes
0answers
29 views

How many expressions can be formed with $k$ commutative and associative functions?

This is a generalization of a question I posted to Math.SE here. Suppose we have $k$ binary functions $f_1, f_2, \ldots, f_k$, all of which are commutative and associative, and $n$ indeterminates ...
11
votes
1answer
130 views

A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I state it in a different but equivalent form. Let $a(n)$ be the sequence at http://oeis.org/A131868, that is, $$ a(n) ...
0
votes
0answers
27 views

Bound from distinct integer summation

We want to find $r$ positive integers $\{a_i\}_{i=1}^r$ such that of atmost $(2s+1)^r$ values obtained from $$\sum_{i=1}s_ia_i$$ where $s_i\in\{-s,-s+1,\dots,0,\dots,s-1,s\}$, we insist on some ...
1
vote
0answers
27 views

Enumerating matrices function of ranks

Is there an expression/approximate expression for number of real matrices $M\in\{0,1\}^{n\times n}$ of rank $r\leq n$?
4
votes
0answers
42 views

Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty). For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$. Given some $1\leq s < d$, consider ...
3
votes
1answer
78 views

A multinomial-type sum over compositions of an integer

I find myself needing to compute (or asymptotically estimate) the following sum over the $2^{S-1}$ compositions of $S$. I am hoping an expert in combinatorics (I am a computer scientist) will ...
11
votes
3answers
245 views

Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...
1
vote
0answers
140 views

Polynomial existence over finite field

Denote $\mathcal{F_n}$ as collection of multiaffine polynomials $f\in\Bbb F_2[x_1,\dots,x_n]$. Denote total degree of $f\in\mathcal{F_n}$ as $deg(f)$ (note $deg(f)\leq n$). Denote ...
1
vote
1answer
92 views

Combinatorics problem involving counting the number of certain substrings

I'm not sure if this question is suited for MO, but it does seem quite challenging to me, and is required for a research problem in chemistry I'm working on. I did try getting help from elsewhere ...
16
votes
2answers
581 views

A possibly surprising appearance of Lucas numbers

Let $S$ be the set of polynomials defined as follows: $0$ is in $S$, and if $p$ is in $S$, then $p + 1$ is in $S$ and $x \cdot p$ is in $S$, so that $S$ "grows" in generations: $g(0)=\{0\}$, ...
2
votes
1answer
71 views

When the vertex covering number is smaller than the chromatic number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ ...
5
votes
0answers
293 views

Survey of Erdős' “Tricks” [on hold]

Is there a kernel of "tricks", techniques and tools that Paul Erdős was particularly fond of and therefore employed a lot in his research work? Could you point out some survey papers that deal with ...
1
vote
0answers
23 views

Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...
4
votes
3answers
87 views

Linear intersection number and vertex covering number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties: for $e\in L$ we have $|e|\geq 2$; if $e_1\neq e_2 \in L$ then ...
4
votes
0answers
69 views

Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?

Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries). Can we partition this union into at most $n$ rectangles? I think it's pretty ...
0
votes
0answers
27 views

About adjacency matrices of $k-$shift lifts of graphs

I am finding the notation of cyclic lifts of graphs to be very confusing. Lets say one is looking at a cyclic $k-$lift of a $\vert V \vert$ sized graph. I would like to understand what is the ...
3
votes
0answers
33 views

Signatures of latin squares: what about the extremal cases?

For a latin square (LS) of order $n$, we will define a cut (or maybe general transversal, I don't know whether there is an entrenched name for this) as a collection of $n$ cells such that no two share ...
4
votes
1answer
176 views

Continuous-piecewise-linear versus piecewise-linear

Some authors use the term "continuous piecewise-linear" where other authors use the shorter term "piecewise-linear" (with continuity tacit). I'd be interested in people's thoughts about this ...
4
votes
1answer
72 views

Compiling self-referential forms

Fix $1\leq d\in\mathbb{N}$ and set $D:=\{0,1,\ldots,d-1\}$. Consider the system of equations \begin{equation} x_i=c_i + \sum_{j\in D}\delta_{x_j,i} \end{equation} with $c_i\in D$ given and $x_i\in D$ ...
1
vote
1answer
168 views

Probabilistic statement on matrix ranks

Given $A\in\{0,1\}^{n\times n}$ with $\operatorname{rank}(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$. Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s. Does ...
4
votes
0answers
128 views

Inversion, Koszul duality, combinatorics and geometry

According to this MO answer Koszul duality is related to operations on generating series; 1) multiplicative inversion for quadratic algebras, 2) compositional inversion for quadratic operads, 3) ...
15
votes
2answers
352 views

Can all unit-distance graphs have their vertices at algebraic integers?

A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$. Obviously, we can ...
8
votes
2answers
219 views

Certain signed sum over $S_n$

The following question appeared in my research: Let $G_1,G_2,G_3$ all be subgroups of $S_n$, and consider the sum $$ \sum_{g_i \in G_i, g_1g_2g_3 = id} \epsilon(g_1) $$ that is, we only consider ...
7
votes
1answer
145 views

A positivity problem involving the number of ways of expressing $n$ as a product of $k$ factors

Let $d_k(n)$ denote the number of ways of expressing $n$ as a product of $k$ factors, and let $$D_k(x)=\sum_{n\leq x}d_k(n)$$ be the summatory function. During a study of Mertens' function I was lead ...
0
votes
3answers
280 views

On independent sets of graph

Given $G$ a regular graph on $n$ vertices, denote $\alpha(G)>1$ to be independence number. Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality ...
5
votes
2answers
290 views

Identity for Power Series and Binomial Coefficients

This question concerns a combinatorial identity obeyed by power series coefficients. Throughout we let $[x^{M}]\{\phi(x)\}$ denote the coefficient of $x^{M}$ in a power series $\phi(x)$. Let $k$ be ...
2
votes
0answers
67 views

Asymptotic expansion for the Bell numbers

The Bell numbers $B(n)$ (that is, the numbers that count the set partitions of a set, and have exponential generating function $\exp(e^x -1)$ ) admit the asymptotic expansion $$\frac{\log B(n)}{n} = ...
2
votes
0answers
85 views

Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...
2
votes
1answer
78 views

Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers

Given $d\in \mathbb{N}$, let $X_d:= \{(\ell_1, \ldots , \ell_d): 0 \le \ell_1 \le \ldots \le \ell_d \le d\}\subset \mathbb{Z}^d$, and endow $X_d$ with the (usual) partial order, namely, $x\le y$ if ...
9
votes
2answers
322 views

Can a graph be reconstructed from its cycle lengths?

All graphs discussed are finite and simple. The cycle sequence of a graph $G$, denoted $C(G)$, is the nondecreasing sequence of the lengths of all of the cycles in $G$, where cycles are distinguished ...
18
votes
1answer
609 views

What are the products $\prod_{A\subset{\mathbb F}_p\colon |A|=n} \sum_{a\in A} \zeta^a$ equal to?

This is a somewhat more explicit version of a question I have recently asked. Let $p$ be an odd prime, and write $\zeta:=\exp(2\pi i/p)$ (any other primitive $p$th root of unity will do as well). For ...
5
votes
1answer
235 views

Infinite graphs isomorphic to their line graph

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example). There are connected countable graphs that are isomorphic to ...
1
vote
0answers
60 views

research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$

Is there any research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$, where $\{\pi_1,\pi_2,...,\pi_{k!}\}=S_k$? I know if we apply the ...
2
votes
1answer
329 views

Is it possible to create an infinite sequence in which no subsequence is repeated 3 times in a row?

In Chess, there is the Threefold Repetition rule where if a sequence of moves is repeated 3 times in a row, either player can claim a draw. Say two players wanted to play a legal, infinite game of ...
3
votes
1answer
111 views

Braid wiring diagrams and matroids

recently I started reading some articles about the presentation of the fundamental group of lines arrangements in $\mathbb{C}^{2}$ via Wiring diagrams. I also found some relation with matroid theory. ...
5
votes
1answer
201 views
+100

Induced subgraphs of small strongly regular graphs

Consider a strongly regular graph $G$ with parameters $(76,30,8,14).$ Hoffman's bound tells us that $\overline{G}$ has an independent set of size at most $4$ and its not hard to see there are indeed ...
4
votes
0answers
57 views

Lower bound on the number of k-plexes in a Latin square

Let $A$ be an order-$n$ Latin square. A $k$-plex of $A$ is a set of entries , $k$ from each row and column and $k$ from each symbol. My question is: Is there a Latin square with a large number of ...
3
votes
1answer
107 views

Infimum of partitions

Let $X\neq\emptyset$ be a set. A partition is a subset $P\subseteq {\cal P}(X)\setminus \{\emptyset\}$ such that $\bigcup P = X$ and any distinct members of $P$ are disjoint. We denote by ...
-1
votes
0answers
80 views

Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$ [migrated]

I'm a bit confused because of the answers in Maximum matchings in infinite graphs . I was thinking that an independent set in a graph $G$ corresponds to a matching in the line graph $L(G)$, and vice ...
3
votes
0answers
61 views

Nonattacking configurations of k bishops on an m by n rectangular board

The number of ways to place k bishops in a nonattacking configuration on an n by n square board is a well known result and can for example be found in ...
0
votes
0answers
36 views

Number of faces of polytope projecting to lower dimensional polyhedron

Denote $K=\mathrm{conv}(v_1, \ldots, v_n)\subsetneq\Bbb R^m$ to be convex set spanned by vectors $v_i\in\Bbb R^m$ with $m\leq n$ then what technique could be useful to upper bound minimum number of ...
3
votes
2answers
286 views

How to flip one triangulation on a surface into another

Let $S$ be a compact orientable surface and $p_1,\dots, p_n\in S$ be distinct points. We consider all triangulations on $S$ with vertices $p_1,\dots, p_n$. Is there an algorithm which takes two ...
2
votes
0answers
75 views

Volume of bounded regions in hyperplane arrangements

I am given a hyperplane arrangement $\mathcal{H}_0$ in $\mathbb{R}^n$ and a function $\phi \colon \mathbb{R}^n \to \mathbb{Q}.$ I choose any enumeration on the set of primitive vectors (i.e. vectors ...
1
vote
0answers
66 views

Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
10
votes
1answer
251 views

Soft question: mathematics about truchet tiles

It seems that this is the first question on Truchet tiles on MO. Shown above is a picture of a random tile, which you can see the resulting configuration is much like many membranes of cells. I ...
1
vote
0answers
33 views

Rook Polynomials of Skew-Ferrers Boards

What are some known method for calculating the rook polynomials of skew Ferrers boards? Currently all I have been able to find is the following paper Bruhat intervals as rooks on skew Ferrers boards ...
0
votes
0answers
62 views

When is edge colored circulant isomorphism polynomial?

Don't understand enough group theory, but two papers appear to give partial results about an open problem. Edge colored graph isomorphism is isomorphism which preserves the edge coloring (the ...
-1
votes
0answers
87 views

Martingales and Bipartite graphs

Would a vertex exposure martingale be useful for bounding the deviation in size of the largest matching from it's expected value in the standard random bipartite graph with vertex classes of size $n$ ...
2
votes
1answer
117 views

NP-hardness of finding maximum of minimum element in diagonal of a matrix

For $A = \{a_{ij}\} \in R^{n\times n}$, is finding $$ \max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i} $$ NP-hard?
1
vote
0answers
87 views

Determining strong base-orderability of a matroid

A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base. ...