Source author record

Meysam Alishahi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

12works
2topics
4close collaborators

Published work

12 publications

preprint2026arXiv

TabKDE: Simple and Scalable Tabular Data Generation with Kernel Density Estimates

Tabular data generation considers a large table with multiple columns -- each column comprised of numerical, categorical, or sometimes ordinal values. The goal is to produce new rows for the table that replicate the distribution of rows from the original data -- without just copying those initial rows. The last 4 years have seen enormous progress on this problem, mostly using computational expensive methods that employ one-hot encoding, VAEs, and diffusion. This paper describes a new approach to the problem of tabular data generation. By employing copula transformations and modeling the distribution as a kernel density estimate we can nearly match the accuracy and leakage-avoidance achievements of the previous methods, but with almost no training time. Our method is very scalable, and can be run on data sets orders of magnitude larger than prior state-of-the-art on a simple laptop. Moreover, because we employ kernel density estimates, we can store the model as a coreset of the original data -- we believe the first for generative modeling -- and as a result, require significantly less space as well. Our code is available here: \url{https://github.com/tabkde/tabkde-main}

preprint2016arXiv

Chromatic Number of Random Kneser Hypergraphs

Recently, Kupavskii~[{\it On random subgraphs of {K}neser and {S}chrijver graphs. J. Combin. Theory Ser. A, {\rm 2016}.}] investigated the chromatic number of random Kneser graphs $\KG_{n,k}(ρ)$ and proved that, in many cases, the chromatic numbers of the random Kneser graph $\KG_{n,k}(ρ)$ and the Kneser graph $\KG_{n,k}$ are almost surely closed. He also marked the studying of the chromatic number of random Kneser hypergraphs $\KG^r_{n,k}(ρ)$ as a very interesting problem. With the help of Zp\Z_p-Tucker lemma, a combinatorial generalization of the Borsuk-Ulam theorem, we generalize Kupavskii's result to random general Kneser hypergraphs by introducing an almost surely lower bound for the chromatic number of them. Roughly speaking, as a special case of our result, we show that the chromatic numbers of the random Kneser hypergraph $\KG^r_{n,k}(ρ)$ and the Kneser hypergraph $\KG^r_{n,k}$ are almost surely closed in many cases. Moreover, restricting to the Kneser and {S}chrijver graphs, we present a purely combinatorial proof for an improvement of Kupavskii's results. Also, for any hypergraph $\HH$, we present a lower bound for the minimum number of colors required in a coloring of $\KG^r(\mathcal{H})$ with no monochromatic Kt,…,trK_{t,\ldots,t}^r subhypergraph, where Kt,…,trK_{t,\ldots,t}^r is the complete rr-uniform rr-partite hypergraph with trt r vertices such that each of its parts has tt vertices. This result generalizes the lower bound for the chromatic number of $\KG^r(\mathcal{H})$ found by the present authors~[{\it On the chromatic number of general {K}neser hypergraphs. J. Combin. Theory, Ser. B, {\rm 2015}.}].

preprint2016arXiv

Circular chromatic number of induced subgraphs of Kneser graphs

Investigating the equality of the chromatic number and the circular chromatic number of graphs has been an active stream of research for last decades. In this regard, Habolhassan and Zhu [Circular chromatic number of Kneser graphs, Journal of Combinatorial Theory Series B, 2003] proved that if nn is sufficiently large with respect to kk, then the Schrijver graph SG(n,k){\rm SG}(n,k) has the same chromatic and circular chromatic number. Later, Meunier [A topological lower bound for the circular chromatic number of Schrijver graphs, Journal of Graph Theory, 2005] and independently, Simonyi and Tardos [ Local chromatic number, Ky Fan's theorem and circular colorings, Combinatorica, 2006] proved that χ(SG(n,k))=χc(SG(n,k))χ({\rm SG}(n,k))=χ_c({\rm SG}(n,k)) if nn is even. In this paper, we study the circular chromatic number of induced subgraphs of Kneser graphs. In this regard, we shall first generalize the preceding result to ss-stable Kneser graphs. Furthermore, as a generalization of Hajiabolhassan and Zhu's result, we prove that if nn is large enough with respect to kk, then any sufficiently large induced subgraph of the Kneser graph KG(n,k){\rm KG}(n,k) has the same chromatic number and circular chromatic number.

preprint2016arXiv

Colorful Subhypergraphs in Uniform Hypergraphs

There are several topological results ensuring the existence of a large complete bipartite subgraph in any properly colored graph satisfying some special topological regularity conditions. In view of Zp\mathbb{Z}_p-Tucker lemma, Alishahi and Hajiabolhassan [{\it On the chromatic number of general Kneser hypergraphs, Journal of Combinatorial Theory, Series B, 2015}] introduced a lower bound for the chromatic number of Kneser hypergraphs KGr(H){\rm KG}^r({\mathcal H}). Next, Meunier [{\it Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014}] improved their result by proving that any properly colored general Kneser hypergraph KGr(H){\rm KG}^r({\mathcal H}) contains a large colorful rr-partite subhypergraph provided that rr is prime. In this paper, we give some new generalizations of Zp\mathbb{Z}_p-Tucker lemma. Hence, improving Meunier's result in some aspects. Some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs are presented as well.

preprint2016arXiv

Hedetniemi's Conjecture Via Altermatic Number

A 5050 years unsolved conjecture by Hedetniemi [{\it Homomorphisms of graphs and automata, \newblock {\em Thesis (Ph.D.)--University of Michigan}, 1966}] asserts that the chromatic number of the categorical product of two graphs GG and HH is min⁡{χ(G),χ(H)}\min\{χ(G),χ(H)\}. The present authors [{\it On the chromatic number of general {K}neser hypergraphs. \newblock {\em Journal of Combinatorial Theory, Series B}, 2015.}] introduced the altermatic and the strong altermatic number of graphs as two tight lower bounds for the chromatic number of graphs. In this work, we prove a relaxation of Hedetniemi's conjecture in terms of strong altermatic number. Also, we present a tight lower bound for the chromatic number of the categorical product of two graphs in term of their altermatic and strong altermatic numbers. These results enrich the family of pair graphs {G,H}\{G,H\} satisfying Hedetniemi's conjecture.

preprint2015arXiv

Chromatic Number Via Turan Number

A Kneser representation KG(H) for a graph G is a bijective assignment of hyperedges of a hypergraph H to the vertices of G such that two vertices of G are adjacent if and only if the corresponding hyperedges are disjoint. In this paper, we introduce a colored version of the Turan number and use that to determine the chromatic number of some families of graphs in terms of the generalized Turan number of graphs. In particular, we determine the chromatic number of every Kneser multigraph KG(H), where the vertex set of H is the edge set of a multigraph G such that the multiplicity of each edge is greater than 1 and a hyperedge in H corresponds to a subgraph of G isomorphic to some graph in a fixed prescribed family of simple graphs.

preprint2015arXiv

On Chromatic Number and Minimum Cut

For a graph GG, the tree graph TG,t{\cal T}_{G,t} has all tree subgraphs of GG with tt vertices as vertex set and two tree subgraphs are neighbors if they are edge-disjoint. Also, the rthr^{th} cut number of GG is the minimum number of edges between parts of a partition of vertex set of GG into two parts such that each part has size at least rr. We show that if t=(1−o(1))nt=(1-o(1))n and nn is large enough, then for any dense graph GG with nn vertices, the chromatic number of the tree graph TG,t{\cal T}_{G,t} is equal to the (n−t+1)th(n-t+1)^{th} cut number of GG. In particular, as a consequence, we prove that if nn is large enough and GG is a dense graph, then the chromatic number of the spanning tree graph TG,n{\cal T}_{G,n} is equal to the size of the minimum cut of GG. The proof method is based on alternating Turán number inspired by Tucker's lemma, an equivalent combinatorial version of the Borsuk-Ulam theorem.

preprint2015arXiv

On The Chromatic Number of Matching Graphs

In an earlier paper, the present authors (2013) introduced the altermatic number of graphs and used Tucker's Lemma, an equivalent combinatorial version of the Borsuk-Ulam Theorem, to show that the altermatic number is a lower bound for the chromatic number. A matching graph has the set of all matchings of a specified size of a graph as vertex set and two vertices are adjacent if the corresponding matchings are edge-disjoint. It is known that the Kneser graphs, the Schrijver graphs, and the permutation graphs can be represented by matching graphs. In this paper, as a generalization of the well-known result of Schrijver about the chromatic number of Schrijver graphs, we determine the chromatic number of a large family of matching graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching graphs in terms of the generalized Turan number of matchings.

preprint2013arXiv

On Chromatic Number of Kneser Hypergraphs

In this paper, in view of ZpZ_p-Tucker lemma, we introduce a lower bound for chromatic number of Kneser hypergraphs which improves Dol'nikov-K{ř}{\'ı}{ž} bound. Next, we introduce multiple Kneser hypergraphs and we specify the chromatic number of some multiple Kneser hypergraphs. For a vector of positive integers s⃗=(s1,s2,…,sm)\vec{s}=(s_1,s_2,\ldots,s_m) and a partition π=(P1,P2,…,Pm)π=(P_1,P_2,\ldots,P_m) of {1,2,…,n}\{1,2,\ldots,n\}, the multiple Kneser hypergraph KGr(π;s⃗;k){\rm KG}^r(π; \vec{s};k) is a hypergraph with the vertex set V={A: A⊆P1∪P2∪⋯∪Pm, ∣A∣=k,∀1≤i≤m; ∣A∩Pi∣≤si}V=\left\{A:\ A\subseteq P_1\cup P_2\cup\cdots \cup P_m,\ |A|=k, \forall 1\leq i\leq m;\ |A\cap P_i|\leq s_i\right\} whose edge set is consist of any rr pairwise disjoint vertices. We determine the chromatic number of multiple Kneser hypergraphs provided that r=2r=2 or for any 1≤i≤m1\leq i\leq m, we have ∣Pi∣≤2si|P_i|\leq 2s_i. A subset S⊆[n]S \subseteq [n] is almost ss-stable if for any two distinct elements i,j∈Si,j\in S, we have ∣i−j∣≥s|i-j|\geq s. The almost ss-stable Kneser hypergraph KGr(n,k)s−stab∼{\rm KG}^r(n,k)_{s-stab}^{\sim} has all ss-stable subsets of [n][n] as the vertex set and every rr-tuple of pairwise disjoint vertices forms an edge. Meunier [The chromatic number of almost stable Kneser hypergraphs. J. Combin. Theory Ser. A, 118(6):1820--1828, 2011] showed for any positive integer rr, χ(KGr(n,k)2−stab∼)=⌈n−r(k−1)r−1⌉χ({\rm KG}^r(n,k)_{2-stab}^{\sim})=\left\lceil {n-r(k-1) \over r-1}\right\rceil. We extend this result to a large family of Schrijver hypergraphs. Finally, we present a colorful-type result which confirms the existence of a completely multicolored complete bipartite graph in any coloring of a graph.

preprint2011arXiv

Dynamic Chromatic Number of Regular Graphs

A dynamic coloring of a graph GG is a proper coloring such that for every vertex v∈V(G)v\in V(G) of degree at least 2, the neighbors of vv receive at least 2 colors. It was conjectured [B. Montgomery. {\em Dynamic coloring of graphs}. PhD thesis, West Virginia University, 2001.] that if GG is a kk-regular graph, then χ2(G)−χ(G)≤2χ_2(G)-χ(G)\leq 2. In this paper, we prove that if GG is a kk-regular graph with χ(G)≥4χ(G)\geq 4, then χ2(G)≤χ(G)+α(G2)χ_2(G)\leq χ(G)+α(G^2). It confirms the conjecture for all regular graph GG with diameter at most 2 and χ(G)≥4χ(G)\geq 4. In fact, it shows that χ2(G)−χ(G)≤1χ_2(G)-χ(G)\leq 1 provided that GG has diameter at most 2 and χ(G)≥4χ(G)\geq 4. Moreover, we show that for any kk-regular graph GG, χ2(G)−χ(G)≤6ln⁡k+2χ_2(G)-χ(G)\leq 6\ln k+2. Also, we show that for any nn there exists a regular graph GG whose chromatic number is nn and χ2(G)−χ(G)≥1χ_2(G)-χ(G)\geq 1. This result gives a negative answer to a conjecture of [A. Ahadi, S. Akbari, A. Dehghan, and M. Ghanbari. \newblock On the difference between chromatic number and dynamic chromatic number of graphs. \newblock {\em Discrete Math.}, In press].

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.