Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged

0

If I understand the problem correctly, then based on YCor's comment, your problem is equivalent to finding a minimum-weight perfect matching on $A \oplus B$, where the weights are given by the metric. If so, then a version of Edmond's "blossom algorithm" should be able to solve it in polynomial time. Check out Kolmogorov's Blossom V: A new implementation of ...


9

The $T_n$'s are equal to the product of $C$ and the Fubini numbers: number of ordered partitions of $n$, also known as ordered Bell numbers. The generating function is $(2-e^x)^{-1}$ and the large-$n$ asymptotics is $$T_n\sim C \frac{n!}{2(\ln 2)^{n+1}}.$$


3

The answer is no. This is equivalent to stating that for any linear hypergraph $H=(\kappa,E)$ with $\kappa$ infinite (note that for $\kappa$ finite, $G=I(H)$ would be finite), we have $\chi(I(H))\leq\kappa$. This follows immediately once we show $|V(I(H))|=|E|\leq\kappa$. For $\alpha<\kappa$ let $E_\alpha=\{e\in E:\alpha\in e\}$. If we remove $\alpha$ ...


1

The specialization $P_\lambda(x;-1)$ is what is referred to as Schur's P functions. They can be described combinatorially using shifted tableaux, and are Schur-positive. See also slides here by S. Cho.


2

Here is a way to formulate it as a convex optimization problem, which can then be solved in polynomial time. Your variables are $a_{i,j}$, one for each position in the matrix. The problem is then: $$0\le a_{i,j} \le 1$$ $$\forall_j \sum_i a_{i,j} = 1$$ $$\forall_i \sum_j a_{i,j} = 1$$ $$\textrm{Minimize } M\bullet a$$ The first constraint defines $a$ as ...


1

Is such generality the result is false. If you have $n$ sets, you can always define ${n \choose 2}$ elements such that each of them is contained in a different couple of sets. This way all the sets have non-empty intersection and no element is contained in more than $2$ sets.


3

This is completely false. Consider the lines of a finite projective plane.


1

each of the $m$ component sequences of your $X$ satisfies a linear recurrence of degree $m$ with characteristic polynomial given by Cayley-Hamilton. The point, I suppose, is that $$ X_{n+j} = A^j X_n $$


2

Here goes the proof of the general fact. At first, we rewrite the product (ignoring the sign) as $\binom{r}{j}\cdot \binom{r+n-j-1}{n-j}$. Denote $r=2^tR$ for odd $R$ and non-negative integer $t$. If $\binom{r}{j}\cdot \binom{r+n-j-1}{n-j}$ is odd, then both $\frac{r}j\binom{r-1}{j-1}=\binom{r}j$ and $\frac{r}{n-j}\cdot \binom{r+n-j-1}{n-j-1}$ are odd. It ...


10

Just for the record: In view of Fedor's nice reply, the interpretation gives away $$\det\left[\binom{i+j+a+b}{i+a}\right]_{i,j=0}^{c-1} =\prod_{i=0}^{a-1}\prod_{j=0}^{b-1}\prod_{k=0}^{c-1} \frac{i+j+k+2}{i+j+k+1}.\tag1$$ An apparent symmetry! As a follow-up to Mark Wildon's comment, let me add the below $q$-construction. Let $(q)_k=(1-q)(1-q^2)\cdots(1-q^...


15

Use Lindstrom-Gessel-Viennot lemma for points $(-a, - j) $ (the first collection of points) and $(i, b) $ (the second collection), both $i, j$ vary from 0 to $c-1$. We see that the determinant counts the families of disjoint lattice paths starting in the points of the first collection and finishing in the second (allowed path directions are North and East). ...


4

The answer is yes for countable graphs: Fix an infinite graph $G$ and a bijective homomorphism $f:G \to G$. Define $c:[G]^2 \to 2$ as $c(\alpha,\beta)=1$ if $\{f\alpha, f\beta\} \in E(G)$ and $c(\alpha,\beta)=0$ otherwise. Since $G$ is infinite, by Ramsey´s Theorem there is an infinite $c$-homogeneous $H \subseteq G$. If $c \upharpoonright [H]^2$ is ...


4

Apparently to avoid perpetual check, a rule was initially set such that a sequence of moves that repeats three times will be declared a draw. A recent nice video by James Grime and Rune Friborg notes that in the 1920's mathematician and chess grandmaster Max Euwe showed that players can engage to create a set of moves corresponding to the Thue-Morse ...


21

This is a very crude attempt to explain the growth rate of $13$, can be almost certainly be improved upon. In the situation where $20$ is the diameter, there are $18$ moves (or monoid generators), with three moves for each face, i.e. two quarter-turns and on half-turn. For each position except for the starting position, moving the same face as on the ...


6

Here is a very simple way to show the positivity. Define $$f(d,x) = (1+x)^d/(1-x)^{d+1}.$$ Then, by induction $$ \frac{\partial^t f(d,x)}{\partial\, d^t} = f(d,x) \, \ln\biggl(\frac{1+x}{1-x}\biggr)^t.$$ Putting in $d=0$ we have that the Taylor series of $f(d,x)$ with respect to $d$ is $$ f(d,x) = \sum_{t=0}^\infty \frac{1}{t!} (1-x)^{-1} \ln\biggl(\frac{...


4

Think of the hypergraph as a simplicial complex $\Delta$, with the facets being the hyperedges. Consider property (*) as: 1) The $i$-skeleton of $\Delta$ is full for $0\leq i\leq k-2$ and 2) $\tilde H_i(\Delta)=0$ for $0\leq i\leq k-2$ Then these conditions force $f_{k-1}-\binom{n-1}{k-1}= \dim \tilde H_{k-1}(\Delta)$. Thus a minimal complex ...


3

Find a nice expression for the number of down-sets (order ideals) of a product of four finite chains (totally ordered sets), $|\bf2^{(\bf k\times \bf m\times \bf n\times \bf r)}|$, where $k,m,n,r$ are positive integers and "$\bf k$" denotes the $k$-element chain, $\{0,1,\dots,k-1\}$. Richard P. Stanley writes (on page 83 of Ordered Structures and Partitions)...


2

A ranked poset is called a symmetric chain order, or SCO, if it can partitioned into rank symmetric, saturated chains. Such posets are particularly nice, as they are rank-symmetric, unimodal, and have the strong Sperner property. If $P$ and $Q$ are SCO's, then so is $P\times Q$. In particular, the Boolean poset ${\bf 2}^n$ of subsets of $\{1,2,\dots,n\}$, ...


3

Let $P,Q$ be posets. Let $Q^P$ denote the poset of order-preserving maps from $P$ to $Q$, where $f\le g$ if $f(p)\le g(p)$ for all $p\in P$. A poset has the fixed point property if for all $f\in P^P$, there exists $p\in P$ such that $f(p)=p$. If $P$ and $Q$ have the fixed point property, does $P\times Q$? Roddy, Rutkowski, and Schroeder proved the answer ...


4

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap A_i \neq \emptyset$ for all $i\in I$. See Conjecture 10.1 in this article by Ron Aharoni and Eli Berger. Interestingly, this conjecture is implied by the ...


6

Let $P$ be a (not necessarily finite) poset such that each element covers and is covered by a finite number of elements. Then we can define the operators $U,D\colon \mathbb{Q}P\to\mathbb{Q}P$ on the vector space of formal linear combinations of elements of $P$ by $U(p) = \sum_{p\lessdot q} q$ and $D(p) = \sum_{q\lessdot p}q$. Such a poset $P$ is called $r$-...


6

What about the Stanley–Stembridge conjecture on (3+1)-free posets? Given a poset $P$ with vertex set $V = \{1,2,\ldots,n\}$, define the symmetric function $X_P$ in countably many indeterminates $x_1, x_2, \ldots$ by $$X_P := \sum_{\kappa:V\to\mathbb{N}} x_{\kappa(1)}x_{\kappa(2)}\cdots x_{\kappa(n)}$$ where the sum is over all maps $\kappa:V \to\mathbb{...


4

Let $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2$ be a boolean function. Ordering $\mathbb{F}_2$ so that $0<1$, we say that $f$ is monotone if $f(x_1,\ldots,x_n) \le f(y_1, \ldots, y_n)$ whenever $x_1 \le y_1, \ldots, x_n \le y_n$. The Dedekind number $M(n)$ is the number of monotone Boolean functions of $n$ variables, up to logical equivalence. ...


11

Here's another classic from algebraic combinatorics. In his PhD thesis "Ordered Structures and Partitions", Stanley introduces the $(P,\omega)$-partition generating function of a labeled poset $(P,\omega)$. This is defined to be $K(P,\omega) := \sum_{\sigma \in A^r(P,\omega)} x^{\sigma}$, where $A^r(P,\omega)$ is the set of all reverse $(P,\omega)$-...


16

Here's a problem that I believe has little chance of being resolved, and it's also not so clear to me what the motivation behind the problem is, but it involves some very pretty algebraic combinatorics. Stanley (in his PhD thesis) defined a poset $P$ to be Gaussian if for every $m\geq 0$ we have $$ \sum_{I \in J(P\times [m])} q^{\#I} = \frac{\prod_{i=1}^{r}(...


21

The 1/3-2/3 conjecture is probably considered one of the most significant open problems about finite posets; see the Wikipedia page: https://en.wikipedia.org/wiki/1/3%E2%80%932/3_conjecture.


0

There is a preprint just posted that claims to disprove it: https://www.preprints.org/manuscript/201902.0059/v1. They show that there is a lower bound for any n which diverges as n increases.


2

In terms of hypergeometric series, the sum is $\binom nk {}_2F_1(-n-1/2, -k; 1/2;1)$, so the identity is a case of the Chu-Vandermonde theorem. It may be obtained from the more "usual-looking" case of Vandermonde's theorem $$\sum_j \binom{k-1/2}{k-j}\binom {n+1/2}{j} = \binom{n+k}{k} $$ by multiplying both sides by $\binom nk/\binom{k-1/2}{k}$ and ...


1

$O(k \log k)$ edges would suffice. So $c(n,k)$ is $O(k \log k)$. We this by showing the following: Thm 1: let $G$ be a graph on $n$ vertices with $n+K$ edges. There are $\theta(K/\log K)$ edge-disjoint cycles in $G$. For the proof of Thm 1, we first define for every graph $G'$, the multigraph $f(G')$ formed from $G'$ by (a) taking the 2-core of $G$ ...


2

This is an extension of the accepted answer. Using it, and ideas from some other papers, I managed to obtain an alternative expression for the generating function which I find interesting. As explained in that answer, the problem reduces to finding $Q(x,0,z):=\sum_{i,\ell}a_{n,1}(\ell)x^nz^\ell$. Let $z=\frac1{q+q^{-1}}$ and $x=-\frac{(1-q) (1-q^2) t}{(1-t)...


2

Looking at (3.20) in Gould's tables, I have an idea of what might be his intended proof of the second identity. At the end of this answer I've indicated a bijective proof, using the same method as Gjergji Zaimi's answer. (This was a comment, but on rereading it, it didn't seem clear to me, so I'e expanded it below.) It suffices to show that $$\tag{$\star$}\...


2

These objects are called linear hypergraphs or partial Steiner systems. However, almost all work on them is confined to the case where the sets (edges, blocks) are all of the same size. This is called $k$-uniform. Let $H(n,k)$ be the number of $k$-uniform linear hypergraphs on $n$ vertices. Then Grable proved $$ \log H(n,k) \sim \frac{k-2}{k(k-1)} n^2\log ...


1

The distribution of component size in Erdos-Renyi networks is discussed in many places, and known analytically. A recent reference that summarizes this is in Appendix A of Eytan Katzav, Ofer Biham, and Alexander K. Hartmann, Distribution of shortest path lengths in subcritical Erdős-Rényi networks, Phys. Rev. E 98, 012301 (2018). I hope this helps


1

For $n$ of the form $6k+1$ or $6k+3,$ a weak lower bound on the number you want is STS$(n)$, the number of Steiner Triple Systems from a set $A$ of size $n$. Such a system is a family of $\frac{n(n-1)}6$ subsets of $A$, all of size $3$, so that each pair is in exactly one triple. It is known that $$STS(n) \gt \left(\frac{n}{e^2}\right)^{n^2/6}.$$ There are ...


1

Here is a better upperbound. Let $n$ be given, and choose $h$ large so that if one chooses $h$ many sets each with $h$ or more elements from $n$, one cannot choose another set without intersecting one of the other sets in two or more elements. $(h^2\gt 2n$ should work.) Then one has at most $2^n$ choose $h$ possibilities for these largish sets in a good ...


2

Here is a quick and dirty upper bound. Estimate the number of subsets of $n$ with three or more elements by $2^n$. Any good collection has at most $n^2/6$ of these sets since the smallest contains 3 of the $n$ choose 2 pairs of elements and no two sets can share a pair. So a good collection can have at most $2^n$ choose $n^2/6$ possibilities for a ...


1

OP: "Is there any literature on this class of graphs?" The term "almost-planar graph" is already firmly in the literature: Guoli Ding, Joshua Fallon, Emily Marshall. "On almost-planar graphs." arXiv abstract. Mar. 2016. "A nonplanar graph $G$ is called almost-planar if for every edge $e$ of $G$, at least one of $G \setminus e$ and $G\,/\,e$ is ...


1

According to Kuratowski's theorem a planar graph is characterized by the absence of (subdivisions of) $K_5$ and $K_{3,3}$, where $K_5$ is the infamous pentagram and $K_{3,3}$ can be visualized as a hexagon with opposite vertices connected by edges and also resembles the smallest Möbius Ladder Graph. My suggestion to construct extremal graph "almost planar"...


2

(It is intended as an extended comment and thinking out loud rather than an answer) That seems that the case when $p$ is a quadrilateral is exactly the bottleneck, the general case will hopefully follow from it by an induction argument. Without loss of generality we can prove the statement for paths of even length (glue a triangle to any edge of an odd-...


1

There is a special version of this question (for $n=15$ and $m\le 7$) at Mathematics.SE. For each $n\ge 2$ I constructed a set $S$ with the property requiring $m\ge \left\lfloor\tfrac n2\right\rfloor=k$. Namely, $$S=A\cup (A-(2^k-1)),$$ where $A=\{1,2,\dots, 2^{k-1}\}$ for even $n$ and $$S= A\cup (A-(2^k-1))\cup \{2(-2^k+2)\}$$ for odd $n\ge 5$, see the ...


2

Well, your addition on the polytope being forced to be Wythoffian definitely guarantees a positive answer. In fact, every Wythoffian polytope with equal sized edges will be uniform. (Vertex transitivity is already contained when asked to be Wythoffian by means of kaleidoscopical construction.) But not every uniform polytope is Wythoffian. Examples are eg. ...


3

I think that the Tutte polynomial, as suggested by Fedor Petrov in the comments, is likely what you are looking for. For a graph $G$, this is the polynomial $$ T(x, y) = \sum_{A \subseteq E(G)} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V(G)|}$$ where $k(A)$ is the number of connected components of $(V(G), A)$. Indeed, the Tutte polynomial is well defined for ...


7

My co-authors (Émilie Charlier, Manon Philibert) and I give positive answers to Grinberg's conjectures in the paper E. Charlier, M. Philibert, M. Stipulanti, Nyldon words. So it is true that there are equally many Nyldon words and Lyndon words of a given length. In addition, we show that the set of Nyldon words is a Hall set (more precisely, we prove that it ...


1

Let $Q(N)$ be the number we are interested in. In Corollary 1 on the paper below it is proven that $Q(N) > 4^{N/5}$ for any $N$ divisible by $5$. They also conjecture that $\lim_{n \to \infty} \frac{log Q(n)}{n \log n} > 0$ Rivin, Igor; Vardi, Ilan; Zimmermann, Paul, The $n$-queens problem, Am. Math. Mon. 101, No. 7, 629-639 (1994). ZBL0825.68479. ...


3

Notice that a map $c : n \to \kappa$ is a coloring of $(n,[n]^k)$ iff no element of $\kappa$ has $k$ distinct preimages. Hence by the pigeonhole principle $\chi((n,[n]^k)) = \lceil\frac{n}{k-1}\rceil$. Now for any $k \geq 3$ and $n > 2k-2$ we have $n > 2$, so $\frac{n}{n-1} < 2 \leq k-1$, implying $\frac{n}{k-1} < n-1$. Thus $\chi((n,[n]^k)) = \...


0

A vertex- and edge-transitive polyhedron is already a uniform polyhedron. This is because the vertex-transitivity asures the vertices to be equivalent and therefore the angles of each face (individually) to be the same. The edge-transitivity then asures the edges to be all of the same size (say unity). And so the faces individually to become regular ones. ...


0

Consider the fact that $$ \prod_{i=1}^k \frac{1}{1-x_i t} = \sum_j h_j(x_1,\dots,x_k) t^j $$ Writing $h_j = h_{j+k-k}$ we get from your first fact: $$ \prod_{i=1}^k \frac{1}{1- i t} = \sum_j S(j+k,k) t^j. $$ Now multiply this by $1/(1-nt)$. We get $$ \sum_j h_j(1,2,\dots,k,n) t^j = \frac{1}{1-nt} \sum_l S(l+k,k) t^l. $$ Comparing the coefficient of $t^j$ on ...


3

Let us introduce the notation $$M:=\max(|A+A|,|A\cdot A|).$$ Your first display implies that either $|A|^3\ll q^{1/2}M^2$ or $|A|^3\ll q^{-1}M^3|A|$. In the first case we get $M\gg q^{-1/4}|A|^{3/2}$ without any assumption on $|A|$. In the second case we get $$M\gg q^{1/3}|A|^{2/3}\gg q^{-1/4}|A|^{3/2},$$ where the second inequality follows from $q^{7/10}\gg ...


8

Yes, the hexagon ABCDEF with the additional edge of AC has this property. The first graph shows $G$ and the others show two views of $D_2(G)$. (Graphs courtesy of NCTM)


2

EDIT: My original answer (below) is correct but not really optimal. This is easier: simply well-order the set of vertices and greedily color them using the well-ordering. More precisely, if you reach a vertex $v$ and have already colored all vertices appearing before $v$ in the well-ordering, color $v$ with the smallest ordinal that does not create a ...


Top 50 recent answers are included