Search ResultsShowing 1-20 of 147
-
arXiv:2505.09809 (Published 2025-05-14)
On Alternating 6-Cycles in Edge-Coloured Graphs
Comments: 19 pages, 2 figuresSubjects: 05C35In this short note, we use flag algebras to prove that the number of colour alternating 6-cycles in a red/blue colouring of a large clique is asymptotically maximized by a uniformly random colouring. This settles the first open case of a problem of Basit, Granet, Horsley, K\"undgen and Staden.
-
A solution to a Paul Erdos problem
Comments: Dear readers, I need to withdraw this paper since I was shown a counterexample. At this moment I cannot fix an error. I shall return to this question as soon as I find a solutionPaul Erdos posed the following question: Is there a prime number $p>5$ such that the residues of $2!$, $3!$,\ldots, $(p-1)!$ modulo $p$ all are distinct? In this short note, we prove that there are no such prime numbers.
-
arXiv:2411.13229 (Published 2024-11-20)
On cospectral graphons
Comments: 7 pagesCategories: math.COIn this short note, we introduce cospectral graphons, paralleling the notion of cospectral graphs. As in the graph case, we give three equivalent definitions: by equality of spectra, by equality of cycle densities, and by a unitary transformation. We also give an example of two cospectral graphons that cannot be approximated by two sequences of cospectral graphs in the cut distance.
-
arXiv:2410.20257 (Published 2024-10-26)
A Short Note on Relevant Cuts
Comments: 7 pagesCategories: math.COThe set of relevant cuts in a graph is the union of all minimum weight bases of the cut space. A cut is relevant if and only if it is the a minimum weight cut between two distinct vertices.
-
arXiv:2409.07877 (Published 2024-09-12)
A new upper bound for codes with a single Hamming distance
Comments: comments are welcomeIn this short note we give a new upper bound for the size of a set family with a single Hamming distance. Our proof is an application of the linear algebra bound method.
-
arXiv:2409.05931 (Published 2024-09-09)
Infinitely many minimally Ramsey size-linear graphs
Comments: 2 pagesCategories: math.COA graph $G$ is said to be Ramsey size-linear if $r(G,H) =O_G (e(H))$ for every graph $H$ with no isolated vertices. Erd\H{o}s, Faudree, Rousseau, and Schelp observed that $K_4$ is not Ramsey size-linear, but each of its proper subgraphs is, and they asked whether there exist infinitely many such graphs. In this short note, we answer this question in the affirmative.
-
arXiv:2408.07056 (Published 2024-08-13)
A short note on spanning even trees
Comments: 6 pagesCategories: math.COWe call a tree $T$ is \emph{even} if every pair of its leaves is joined by a path of even length. Jackson and Yoshimoto\cite{jacksonspanning}~[J. Graph Theory, 2024] conjectured that every $r$-regular nonbipartite connected graph $G$ has a spanning even tree. They verified this conjecture for the case when $G$ has a $2$-factor. In this paper, we prove that the conjecture holds when $r$ is odd, thereby resolving the only remaining unsolved case for this conjecture.
-
arXiv:2408.00484 (Published 2024-08-01)
On set systems without singleton intersections
Categories: math.COConsider a family $\mathcal{F}$ of $k$-subsets of an ambient $(k^2-k+1)$-set such that no pair of $k$-subsets in $\mathcal{F}$ intersects in exactly one element. In this short note we show that the maximal size of such $\mathcal{F}$ is $\binom{k^2-k-1}{k-2}$ for every $k > 1$.
-
arXiv:2407.14084 (Published 2024-07-19)
A Purely Entropic Approach to the Rainbow Triangle Problem
Comments: 5 pages, 5 figuresIn this short note, we present a purely entropic proof that in a $3$-edge-colored simple graph with $R$ red edges, $G$ green edges, and $B$ blue edges, the number of rainbow triangles is at most $\sqrt{2RGB}$.
-
arXiv:2405.18162 (Published 2024-05-28)
A note on locating sets in twin-free graphs
Comments: 5 pages, 1 figureCategories: math.COIn this short note, we prove that every twin-free graph on $n$ vertices contains a locating-dominating set of size at most $\lceil\frac{5}{8}n\rceil$. This improves the earlier bound of $\lfloor\frac{2}{3}n\rfloor$ due to Foucaud, Henning, L\"owenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, Gonz\'alez and M\'arquez.
-
arXiv:2403.19249 (Published 2024-03-28)
Hadwiger's conjecture holds for strongly monotypic polytopes
Comments: 6 pages; comments are welcomeIn this short note, we prove Hadwiger's conjecture for strongly monotypic polytopes.
-
$C_{10}$ has positive Turán density in the hypercube
Comments: 5 pagesCategories: math.COThe $n$-dimensional hypercube $Q_n$ is a graph with vertex set $\{0,1\}^n$ and there is an edge between two vertices if they differ in exactly one coordinate. For any graph $H$, define $\text{ex}(Q_n,H)$ to be the maximum number of edges of a subgraph of $Q_n$ without a copy of $H$. In this short note, we prove that for any $n \in \mathbb{N}$ $$\text{ex}(Q_n, C_{10}) > 0.024 \cdot e(Q_n).$$ Our construction is strongly inspired by the recent breakthrough work of Ellis, Ivan, and Leader, who showed that "daisy" hypergraphs have positive Tur\'an density with an extremely clever and simple linear-algebraic argument.
-
arXiv:2312.08114 (Published 2023-12-13)
A note on hook length equidistribution on arithmetic progressions
Comments: Short 8-page noteCategories: math.COIn a recent paper, Bringmann, Craig, Ono, and the author showed that the number of $t$-hooks ($t\geq2$) among all partitions of $n$ is not always asymptotically equidistributed on congruence classes $a \pmod{b}$. In this short note, we clarify the situation of $t=1$, i.e. all hook lengths, and show that this case does give asymptotic equidistribution, closing the story of the distribution properties of $t$-hooks on congruence classes.
-
arXiv:2312.01822 (Published 2023-12-04)
Note on Minkowski Summation and Unimodularity in Discrete Convex Analysis
Comments: 9 pagesCategories: math.COThis short note gives an elementary alternative proof for a theorem of Danilov and Koshevoy on Minkowski summation and unimodularity in discrete convex analysis. It is intended to disseminate this fundamental theorem and make its proof accessible to researchers in optimization and operations research.
-
arXiv:2309.00757 (Published 2023-09-01)
A Note on Hamiltonian-Intersecting Families of Graphs
How many graphs on an $n$-point set can we find such that any two have connected intersection? Berger, Berkowitz, Devlin, Doppelt, Durham, Murthy and Vemuri showed that the maximum is exactly $1/2^{n-1}$ of all graphs. Our aim in this short note is to give a 'directed' version of this result; we show that a family of oriented graphs such that any two have strongly-connected intersection has size at most $1/3^n$ of all oriented graphs. We also show that a family of graphs such that any two have Hamiltonian intersection has size at most $1/2^n$ of all graphs, verifying a conjecture of the above authors.
-
arXiv:2308.04155 (Published 2023-08-08)
A short note on the order of the double reduced 2-factor transfer digraph for rectangular grid graphs
Comments: 8 pages, 3 figuresCategories: math.COWe prove that the order of the double reduced 2-factor transfer digraph ${\cal R}^{**}_{m}$ which is needed for the enumeration of the spanning unions of cycles in the rectangular grid graph $P_m \times P_n$ ($m,n \in N$), when $m$ is odd, is equal to $\displaystyle \mid V({\cal R}^{**}_{m}) \mid = \frac{1}{2} \left[{m+1 \choose (m-1)/2 } + {(m+1)/2 \choose \lfloor (m+1)/4 \rfloor}\right].$
-
arXiv:2308.00340 (Published 2023-08-01)
A short note on cospectral and integral chain graphs for Seidel matrix
In this brief communication, we investigate the cospectral as well integral chain graphs for Seidel matrix, a key component to study the structural properties of equiangular lines in space. We derive a formula that allows to generate an infinite number of inequivalent chain graphs with identical spectrum. In addition, we obtain a family of Seidel integral chain graphs. This contrapositively answers a problem posed by Greaves ["Equiangular line systems and switching classes containing regular graphs", Linear Algebra Appl., (2018)] ("Does every Seidel matrix with precisely three distinct rational eigenvalues contain a regular graph in its switching class?"). Our observation is- "no".
-
arXiv:2306.13014 (Published 2023-06-22)
The binomial random graph is a bad inducer
Comments: 4 pages; comments welcome!Categories: math.COFor a finite graph $F$ and a value $p \in [0,1]$, let $I(F,p)$ denote the largest $y$ for which there is a sequence of graphs of edge density approaching $p$ so that the induced $F$-density of the sequence approaches $y$. In this short note, we show that for all $F$ on at least three vertices and $p \in (0,1)$, the binomial random graph $G(n,p)$ has induced $F$-density strictly less than $I(F,p).$ This provides a negative answer to a problem posed by Liu, Mubayi and Reiher.
-
arXiv:2305.18252 (Published 2023-05-29)
On MaxCut and the Lovász theta function
Comments: 7 pagesCategories: math.COIn this short note we prove a lower bound for the MaxCut of a graph in terms of the Lov\'asz theta function of its complement. We combine this with known bounds on the Lov\'asz theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$.
-
arXiv:2305.02648 (Published 2023-05-04)
A short note on the characterization of countable chains with finite big Ramsey spectra
In this short note we build on a recent result by Ma\v{s}ulovi\'{c} to provide a complete characterization of countable chains (i.e.\ strict linear orders) whose big Ramsey spectra are finite.