Search Results

The answer to Question 1 is negative. Let $G=\{\{1, \dots, N+1\}\}$ and $H$ consist of all subsets of $\{1, \dots, N+1\}$ of size $N$. If $K$ is a distinguisher for $G$ and $H$, then for each $i \in …

Yes. Just take $\mathcal{A}$ to be $[\omega]^2$ together with the powerset of the even integers.

Here is a proof of Conjecture 1. Proof. We prove the contrapositive. Suppose that $G$ is not a cograph. Then $G$ has an induced subgraph $H$ such that $H \simeq P_4$. Let $V(H)=\{1,2,3,4\}$ and …

Yes, we may take the function to be $2\Delta$. Lemma. Every interval graph $G$ has an interval representation where all intervals have length between $1$ and $2\Delta$, where $\Delta$ is the maximum d …

The following puzzle can be solved by the same technique. A mountain range is a piecewise linear function $f$ defined on a closed interval $[a,b]$ which satisfies $f(a)=f(b)=0$, and $f(c) > 0$ for al …

Here are some upper and lower bounds. The paper On the chromatic number of some flip graphs proves that the chromatic number of $G_k$ is at most $4k-4$. Therefore, in every proper colouring of $G_k$ t …

Here is a bijective proof. Label the vertices of $C_{2n}$ as $1, 2, \dots, n, 1', 2', \dots, n'$ in clockwise order and let $M$ be a matching of size $k<n$ in $C_{2n}$. Since $M$ is not a perfect mat …

This is a design theory question. You are asking about the existence of a Balanced Incomplete Block Design (BIBD). A $(v,k,t,\lambda)$-design is a collection of $k$-subsets (called blocks) of a $v$- …

Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. In case you cannot access the paper, the relevant theorem is Theorem 5.9. If $G$ is an obstruc …

No, this is false even in the planar case. Let $G=W_n$ be a wheel graph with $n \geq 6$. Deleting any edge of the outercycle yields a fan graph, which is not $3$-connected. On the other hand, contr …

Update. The recent paper Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^d$ by Soma Villányi gives a positive answer to the question. Old Answer. I think this is still an open problem, …

Here is a short proof that at most $2n-2$ swaps are necessary. We proceed by induction on $n$. For the base case $n=1$, it is clear that no swaps are necessary. For the inductive step, let $X_1,X_2 …

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, …

This is false in general. Let $X=\{1, \dots, n+1\}$, $Y=\{n+1, \dots, 2n+1\}$, and $Z$ be any $(n+1)$-subset of $[2n+1]$ not containing $n+1$. Let $\mathcal{F}=\mathcal{A} \setminus \{X,Y,Z\}$. The …

According to Gallai’s question and constructions of almost hypotraceable graphs by Wiener and Zamfirescu, this is an open problem (see the beginning of Section 4). Note that a graph is $G$ hypotrace …