Source author record

Hamza Si Kaddour

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the Boolean dimension of a graph and other related parameters

We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions, and with the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.

preprint2015arXiv

Isomorphy up to complementation

Considering uniform hypergraphs, we prove that for every non-negative integer $h$ there exist two non-negative integers $k$ and $t$ with $k\leq t$ such that two $h$ -uniform hypergraphs ${\mathcal H}$ and ${\mathcal H}'$ on the same set $V$ of vertices, with $| V| \geq t$ , are equal up to complementation whenever ${\mathcal H}$ and ${\mathcal H}'$ are $k$ -{hypomorphic up to complementation}. Let $s(h)$ be the least integer $k$ such that the conclusion above holds and let $v(h)$ be the least $t$ corresponding to $k=s(h)$ . We prove that $s(h)= h+2^{\lfloor \log_2 h\rfloor}$ . In the special case $h=2^{\ell}$ or $h=2^{\ell}+1$ , we prove that $v(h)\leq s(h)+h$ . The values $s(2)=4$ and $v(2)=6$ were obtained in a previous work.

preprint2013arXiv

On a generalization of Kelly's combinatorial lemma

Kelly's combinatorial lemma is a basic tool in the study of Ulam's reconstruction conjecture. A generalization in terms of a family of t-elements subsets of a v-element set was given by Pouzet. We consider a version of this generalization modulo a prime p. We give illustrations to graphs and tournaments.

preprint2006arXiv

Hypomorphy of graphs up to complementation

Let $V$ be a set of cardinality $v$ (possibly infinite). Two graphs $G$ and $G'$ with vertex set $V$ are {\it isomorphic up to complementation} if $G'$ is isomorphic to $G$ or to the complement $\bar G$ of $G$ . Let $k$ be a non-negative integer, $G$ and $G'$ are {\it $k$ -hypomorphic up to complementation} if for every $k$ -element subset $K$ of $V$ , the induced subgraphs $G\_{\restriction K}$ and $G'\_{\restriction K}$ are isomorphic up to complementation. A graph $G$ is {\it $k$ -reconstructible up to complementation} if every graph $G'$ which is $k$ -hypomorphic to $G$ up to complementation is in fact isomorphic to $G$ up to complementation. We give a partial characterisation of the set $\mathcal S$ of pairs $(n,k)$ such that two graphs $G$ and $G'$ on the same set of $n$ vertices are equal up to complementation whenever they are $k$ -hypomorphic up to complementation. We prove in particular that $\mathcal S$ contains all pairs $(n,k)$ such that $4\leq k\leq n-4$ . We also prove that 4 is the least integer $k$ such that every graph $G$ having a large number $n$ of vertices is $k$ -reconstructible up to complementation; this answers a question raised by P. Ille

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.