Source author record

Sven Polak

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

ResearcherUnclaimed source record

math.CO math.OC Information Theory math.IT

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Semidefinite approximations for bicliques and biindependent pairs

We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$ , i.e., pairs $(A,B)$ where $A\subseteq V_1$ , $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $α(G)$ , well-known to be polynomial-time computable. When maximizing the product $|A|\cdot |B|$ one finds the parameter $g(G)$ , shown to be NP-hard by Peeters (2003), and when maximizing the ratio $|A|\cdot |B|/|A\cup B|$ one finds $h(G)$ , introduced by Vallentin (2020) for bounding product-free sets in finite groups. We show that $h(G)$ is an NP-hard parameter and, as a crucial ingredient, that it is NP-complete to decide whether a bipartite graph $G$ has a balanced maximum independent set. These hardness results motivate introducing semidefinite programming bounds for $g(G)$ , $h(G)$ , and $α_{\text{bal}}(G)$ (the maximum cardinality of a balanced independent set). We show that these bounds can be seen as natural variations of the Lovász $\vartheta$ -number, a well-known semidefinite bound on $α(G)$ . In addition we formulate closed-form eigenvalue bounds and we show relationships among them as well as with earlier spectral parameters by Hoffman, Haemers (2001) and Vallentin (2020).

preprint2022arXiv

The maximum cardinality of trifferent codes with lengths 5 and 6

A code $\mathcal{C} \subseteq \{0, 1, 2\}^n$ is said to be trifferent with length $n$ when for any three distinct elements of $\mathcal{C}$ there exists a coordinate in which they all differ. Defining $\mathcal{T}(n)$ as the maximum cardinality of trifferent codes with length $n$ , $\mathcal{T}(n)$ is unknown for $n \ge 5$ . In this note, we use an optimized search algorithm to show that $\mathcal{T}(5) = 10$ and $\mathcal{T}(6) = 13$ .

preprint2021arXiv

Symmetry reduction to optimize a graph-based polynomial from queueing theory

For given integers $n$ and $d$ , both at least 2, we consider a homogeneous multivariate polynomial $f_d$ of degree $d$ in variables indexed by the edges of the complete graph on $n$ vertices and coefficients depending on cardinalities of certain unions of edges. Cardinaels, Borst and Van Leeuwaarden (arXiv:2111.05777, 2021) asked whether $f_d$ , which arises in a model of job-occupancy in redundancy scheduling, attains its minimum over the standard simplex at the uniform probability vector. Brosch, Laurent and Steenkamp [SIAM J. Optim. 31 (2021), 2227--2254] proved that $f_d$ is convex over the standard simplex if $d=2$ and $d=3$ , implying the desired result for these $d$ . We give a symmetry reduction to show that for fixed $d$ , the polynomial is convex over the standard simplex (for all $n\geq 2$ ) if a constant number of constant matrices (with size and coefficients independent of $n$ ) are positive semidefinite. This result is then used in combination with a computer-assisted verification to show that the polynomial $f_d$ is convex for $d\leq 9$ .

preprint2020arXiv

New Methods in Coding Theory: Error-Correcting Codes and the Shannon Capacity

In this thesis we present several results in coding theory, concerning error-correcting codes and the Shannon capacity. 1. We give a general symmetry reduction of matrices occuring in semidefinite programs in coding theory. 2. We apply the symmetry reduction to efficiently compute semidefinite programming upper bounds for nonbinary error-correcting codes equipped with the Hamming distance (joint work with Bart Litjens and Lex Schrijver), with the Lee distance and for binary constant weight codes. 3. We explore other methods to find new upper bounds for nonbinary codes with the Hamming distance, based on combinatorial divisibility arguments. 4. We study uniqueness and classification of codes, using the output of the semidefinite programming solver. Most of our classification results are related to subcodes of the binary Golay code. This is joint work with Andries Brouwer. 5. We consider the Shannon capacity of circular graphs. The circular graph $C_{d,q}$ is the graph with vertex set $\mathbb{Z}_q$ (the cyclic group of order q) in which two distinct vertices are adjacent if and only if their distance (mod $q$ ) is strictly less than $d$ . The Shannon capacity of $C_{d,q}$ can be seen to only depend on the fraction q/d. We prove that the function which assigns to each rational number $q/d$ the Shannon capacity of $C_{d,q}$ is continuous at integer points $q/d$ . Moreover, we give a new lower bound on the Shannon capacity of the $7$ -cycle. This is joint work with Lex Schrijver. This thesis was written at the University of Amsterdam under supervision of Lex Schrijver.

preprint2017arXiv

Sum-perfect graphs

Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph $G$ to be sum-perfect if for every induced subgraph $H$ of $G$ , $α(H) + ω(H) \geq |V(H)|$ . (Here $α$ and $ω$ denote the stability number and clique number, respectively.) We give a set of $27$ graphs and we prove that a graph $G$ is sum-perfect if and only if $G$ does not contain any of the graphs in the set as an induced subgraph.

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.