Search ResultsShowing 1-20 of 49
-
arXiv:2412.13485 (Published 2024-12-18)
Dense halves in balanced 2-partition of K4-free graphs
Comments: 18 pages, 3 figuresCategories: math.COA balanced 2-partition of a graph is a bipartition $A,A^c$ of $V(G)$ such that $|A|=|A^c|$. Balogh, Clemen, and Lidick\'y conjectured that for every $K_4$-free graph on $n$ (even) vertices, there exists a balanced 2-partition $A,A^c$ such that $\max\{e(A),e(A^c)\}\leq n^2/16$ edges. In this paper, we present a family of counterexamples to the conjecture and provide a new upper bound ($0.074n^2$) for every sufficiently large even integer $n$.
-
arXiv:2411.09701 (Published 2024-11-14)
Counterexamples to Zagier's Duality Conjecture on Nahm Sums
Comments: First versionGiven any positive integer $r$, Nahm's problem is to determine all rational $r\times r$ positive definite matrix $A$, $r$-dimensional rational vector $B$ and rational scalar $C$ such that the rank $r$ Nahm sum associated with $(A,B,C)$ is modular. Around 2007, Zagier conjectured that if the rank $r$ Nahm sum for $(A,B,C)$ is modular, then so is the dual Nahm sum associated with $(A^{-1},A^{-1}B,B^\mathrm{T} A^{-1}B/2-{r}/{24}-C)$. We construct some explicit rank four Nahm sums wherein the original Nahm sum is modular while its dual is not modular. This provides counterexamples to Zagier's conjecture.
-
arXiv:2405.01890 (Published 2024-05-03)
Counterexamples to two conjectures on mean color numbers of graphs
Comments: 5 pagesCategories: math.COThe mean color number of an $n$-vertex graph $G$, denoted by $\mu(G)$, is the average number of colors used in all proper $n$-colorings of $G$. For any graph $G$ and a vertex $w$ in $G$, Dong (2003) conjectured that if $H$ is a graph obtained from a graph $G$ by deleting all but one of the edges which are incident to $w$, then $\mu(G)\geq \mu(H)$; and also conjectured that $\mu(G)\geq \mu((G-w)\cup K_1)$. We prove that there is an infinite family of counterexamples to these two conjectures.
-
arXiv:2401.00807 (Published 2024-01-01)
An infinite family of counterexamples to a conjecture on distance magic labeling
Categories: math.COThis work is about a partition problem which is an instance of the distance magic graph labeling problem. Given positive integers $n,k$ and $p_1\le p_2\le \cdots\le p_k$ such that $p_1+\cdots+p_k=n$ and $k$ divides $\sum_{i=1}^ni$, we study the problem of characterizing the cases where it is possible to find a partition of the set $\{1,2,\ldots,n\}$ into $k$ subsets of respective sizes $p_1,\dots,p_k$, such that the element sum in each subset is equal. Using a computerized search we found examples showing that the necessary condition, $\sum_{i=1}^{p_1+\cdots+p_j} (n-i+1)\ge j{\binom{n+1}{2}}/k$ for all $j=1,\ldots,k$, is not generally sufficient, refuting a past conjecture. Moreover, we show that there are infinitely many such counter-examples. The question whether there is a simple characterization is left open and for all we know the corresponding decision problem might be NP-complete.
-
arXiv:2311.05542 (Published 2023-11-09)
Counterexamples to conjectures on the occupancy fraction of graphs
Comments: 8 pages, 3 figuresCategories: math.COThe occupancy fraction of a graph is a (normalized) measure on the size of independent sets under the hard-core model, depending on a variable (fugacity) $\lambda.$ We present a criterion for finding the graph with minimum occupancy fraction among graphs with a fixed order, and disprove five conjectures on the extremes of the occupancy fraction and (normalized) independence polynomial for certain graph classes of regular graphs with a given girth.
-
arXiv:2307.10852 (Published 2023-07-20)
Examples and counterexamples in Ehrhart theory
Comments: Comments welcome!This article provides a comprehensive exposition about inequalities that the coefficients of Ehrhart polynomials and $h^*$-polynomials satisfy under various assumptions. We pay particular attention to the properties of Ehrhart positivity as well as unimodality, log-concavity and real-rootedness for $h^*$-polynomials. We survey inequalities that arise when the polytope has different normality properties. We include statements previously unknown in the Ehrhart theory setting, as well as some original contributions in this topic. We address numerous variations of the conjecture asserting that IDP polytopes have a unimodal $h^*$-polynomial, and construct concrete examples that show that these variations of the conjecture are false. Explicit emphasis is put on polytopes arising within algebraic combinatorics. Furthermore, we describe and construct polytopes having pathological properties on their Ehrhart coefficients and roots, and we indicate for the first time a connection between the notions of Ehrhart positivity and $h^*$-real-rootedness. We investigate the log-concavity of the sequence of evaluations of an Ehrhart polynomial at the non-negative integers. We conjecture that IDP polytopes have a log-concave Ehrhart series. Many additional problems and challenges are proposed.
-
arXiv:2207.08007 (Published 2022-07-16)
A family of counterexamples for a conjecture of Berge on $α$-diperfect digraphs
Let $D$ be a digraph. A stable set $S$ of $D$ and a path partition $\mathcal{P}$ of $D$ are orthogonal if every path $P \in \mathcal{P}$ contains exactly one vertex of $S$. In 1982, Berge defined the class of $\alpha$-diperfect digraphs. A digraph $D$ is $\alpha$-diperfect if for every maximum stable set $S$ of $D$ there is a path partition $\mathcal{P}$ of $D$ orthogonal to $S$ and this property holds for every induced subdigraph of $D$. An anti-directed odd cycle is an orientation of an odd cycle $(x_0,\ldots,x_{2k},x_0)$ with $k\geq2$ in which each vertex $x_0,x_1,\ldots,x_{2k-1}$ is either a source or a sink. Berge conjectured that a digraph $D$ is $\alpha$-diperfect if and only if $D$ does not contain an anti-directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not $\alpha$-diperfect.
-
arXiv:2205.00426 (Published 2022-05-01)
Counterexamples to Gerbner's Conjecture on Stability of Maximal $F$-free Graphs
Comments: 20pages,1 figuresCategories: math.COLet $F$ be an $(r+1)$-color critical graph with $r\geq 2$, that is, $\chi(F)=r+1$ and there is an edge $e$ in $F$ such that $\chi(F-e)=r$. Gerber recently conjectured that every $n$-vertex maximal $F$-free graph with at least $(1-\frac{1}{r})\frac{n^2}{2}- o(n^{\frac{r+1}{r}})$ edges contains an induced complete $r$-partite graph on $n-o(n)$ vertices. Let $F_{s,k}$ be a graph obtained from $s$ copies of $C_{2k+1}$ by sharing a common edge. In this paper, we show that for all $k\geq 2$ if $G$ is an $n$-vertex maximal $F_{s,k}$-free graph with at least $n^{2}/4 - o(n^{\frac{s+2}{s+1}})$ edges, then $G$ contains an induced complete bipartite graph on $n-o(n)$ vertices. We also show that it is best possible. This disproves Gernber's conjecture for $r=2$.
-
arXiv:2202.07529 (Published 2022-02-15)
Counterexamples to the characterisation of graphs with equal independence and annihilation number
We disprove the characterisation of graphs with equal independence and annihilation number by Larson and Pepper (2011). Series of counterexamples with arbitrary number of vertices, arbitrary number of components, arbitrary large independence number and arbitrary large difference between the critical and the regular independence number are provided. Furthermore, we point out the error in the proof of the theorem. However, we show that the theorem still holds for bipartite graphs and connected claw-free graphs.
-
arXiv:2108.07680 (Published 2021-08-17)
Counterexamples to the Colorful Tverberg Conjecture for Hyperplanes
Comments: 5 pagse, 1 figureCategories: math.COIn 2008 Karasev conjectured that for every set of $r$ blue lines, $r$ green lines, and $r$ red lines in the plane, there exists a partition of them into $r$ colorful triples whose induced triangles intersect. We disprove this conjecture for every $r$ and extend the counterexamples to higher dimensions.
-
arXiv:2107.04998 (Published 2021-07-11)
Counterexamples to a conjecture on matching Kneser graphs
Comments: 1 pageCategories: math.COLet $G$ be a graph and $r\in\mathbb{N}$. The matching Kneser graph $\textsf{KG}(G, rK_2)$ is a graph whose vertex set is the set of $r$-matchings in $G$ and two vertices are adjacent if their corresponding matchings are edge-disjoint. In [Alishahi, M. and Hajiabolhassan, H., On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput. 29 (2020), no. 1, 1--21.] it was conjectured that for any connected graph $G$ and positive integer $r\geq 2$, the chromatic number of $\textsf{KG}(G, rK_2)$ is equal to $|E(G)|-\textsf{ex}(G,rK_2)$, where $\textsf{ex}(G,rK_2)$ denotes the largest number of edges in $G$ avoiding a matching of size $r$. In this note, we show that the conjecture is not true for snarks.
-
arXiv:2101.09319 (Published 2021-01-22)
On a conjecture of Gross, Mansour and Tucker
Partial duality is a duality of ribbon graphs relative to a subset of their edges generalizing the classical Euler-Poincare duality. This operation often changes the genus. Recently J.L.Gross, T.Mansour, and T.W.Tucker formulated a conjecture that for any ribbon graph different from plane trees and their partial duals, there is a subset of edges partial duality relative to which does change the genus. A family of counterexamples was found by Qi Yan and Xian'an Jin. In this note we prove that essentially these are the only counterexamples.
-
arXiv:2009.05950 (Published 2020-09-13)
Counterexamples to the interpolating conjecture on partial-dual genus polynomials of ribbon graphs
Comments: 10 pages, 5 figuresCategories: math.COGross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They showed that the partial-dual genus polynomial for an orientable ribbon graph is interpolating and gave an analogous conjecture: The partial-dual Euler-genus polynomial for any non-orientable ribbon graph is interpolating. In this paper, we first give some counterexamples to the conjecture. Then motivated by these counterexamples, we further find two infinite families of counterexamples.
-
arXiv:2009.00423 (Published 2020-08-30)
Counterexamples to a conjecture of Merker on 3-connected cubic planar graphs with a large cycle spectrum gap
Comments: 3 pages, 2 figuresCategories: math.COMerker conjectured that if $k \ge 2$ is an integer and $G$ a 3-connected cubic planar graph of circumference at least $k$, then the set of cycle lengths of $G$ must contain at least one element of the interval $[k, 2k+2]$. We here prove that for every even integer $k \ge 6$ there is an infinite family of counterexamples.
-
arXiv:2004.01327 (Published 2020-04-03)
Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]
Categories: math.CORecently, Huang [arXiv:1907.00847] gave a very elegant proof of the Sensitivity Conjecture by proving that hypercube graphs have the following property: every induced subgraph on a set of more than half the vertices has maximum degree at least $\sqrt{d}$, where $d$ is the valency of the hypercube. This was generalised by Alon and Zheng [arXiv:2003.04926] who proved that every Cayley graph on an elementary abelian $2$-group has the same property. Very recently, Potechin and Tsang [arXiv:2003.13166] proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We give an infinite family of counterexamples to this conjecture.
-
arXiv:1912.00282 (Published 2019-11-30)
Counterexamples to Siegel's Conjecture
Comments: 28 pagesWe prove that the intersection of a Hirsch polytope and a cube may be a non-Hirsch polytope.
-
arXiv:1908.06697 (Published 2019-08-19)
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
Categories: math.COWe construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.
-
arXiv:1905.02167 (Published 2019-05-06)
Counterexamples to Hedetniemi's conjecture
Comments: 3 pagesCategories: math.COThe chromatic number of $G\times H$ can be smaller than the minimum of the chromatic numbers of finite simple graphs $G$ and $H$.
-
arXiv:1902.05701 (Published 2019-02-15)
On a conjecture of Bondy and Vince
Categories: math.COTwenty years ago Bondy and Vince conjectured that for any nonnegative integer $k$, except finitely many counterexamples, every graph with $k$ vertices of degree less than three contains two cycles whose lengths differ by one or two. The case $k\leq 2$ was proved by Bondy and Vince, which resolved an earlier conjecture of Erd\H{o}s et. al.. In this paper we confirm this conjecture for all $k$.
-
arXiv:1901.00440 (Published 2018-12-20)
On a question of Sidorenko
Categories: math.COFor a positive integer $n>1$ denote by $\omega(n)$ the maximal possible number $k$ of different functions $f_1,\dots,f_k:\mathbb{Z}/n\mathbb{Z}\mapsto \mathbb{Z}/n\mathbb{Z}$ such that each function $f_i-f_j,i<j$, is bijective. Recently A. Sidorenko conjectured that $\omega(n)$ equals to the minimal prime divisor of $n$. We disprove it for $n=15,21,27$ by several counterexamples found by computer.